백준 - 비숍 (1799)

1799번: 비숍

결국엔 힌트를 보고 풀었습니다. 구현까진 어떻게 했는 데, TLE에서 더 이상 버티지 못했습니다. NMK를 풀 수 있었던건, 정답을 맞추면 되는 문제였지만 이 문제는 최적화 까지 요구를 했었기 때문에 중간에 주저앉아 버린 것 같군요.

 

N크기의 체스판, 몇 개의 장애물에 비숍을 세울 수 있는 크기를 구하는 문제로, 그냥 보면 단순히 백트래킹 돌리면 되어 보이는 문제 이지만 실상은 그렇지 않습니다. 바로 TLE가 뜨기 때문에 좀더 빠른 시간 안에 구하는 방법을 찾아야 합니다.

 

비숍의 특징은 대각선 방향으로 상대 말을 잡을 수 있다는 점입니다. 그렇다면 아래와 같이 체스판을 하양/검정으로 반복해서 칠한다면, 비숍을 놓을 때 검정색에 놓이면 검정색만 접근하게 되고, 반대로 하얀색에 놓으면 하얀색만 접근하게 됩니다.

결국 검정과 하양은 서로 영향을 미치지 않으므로 체스판을 검정색일 경우와 하얀색의 경우로 나눠 (N*N)/2 형태로 만든 다음 각각 백트래킹을 돌려 두 개의 경우의 수를 합하면 되는 문제였습니다.

 

지금 까지 백트래킹 문제를 풀어봤지만 이렇게 최적화를 하는 백트래킹 문제는 이번이 처음이군요. 최근에 2048(Hard) 문제에 눈독을 들이고 있긴 한데 아마 같은 테크닉으로 푸는 문제인 것 같습니다. 주말에 시간 널널할 때 이 문제도 풀어봐야 겠군요.

 

코드(C)

#include <stdio.h>
#include <stdlib.h>

#define BISHOP	1

int g[10][10], dp[10][10][10][10], b[100][2], bi=0;
int n,ans_b=0,ans_w=0;

int di[4] = {1,1,-1,-1};
int dj[4] = {1,-1,1,-1};

void solution(int ci, int cj, int color)
{
	register int i,j,k,m;
	if(color) m = 1;
	else m = 0;
	for(i=ci;i<n;i++)
	{
		if(i==ci) j=cj;
		// 색깔에 따라 j는 다르게 지정한다.
		else j = !(i%2) ? color : (color+1)%2;
		for(;j<n;j+=2)
		{
			int failed = 0;
			if(!g[i][j]) continue;
			for(k=0;k<bi;k++)
			{
				if(dp[b[k][0]][b[k][1]][i][j] == BISHOP)
				{
					failed = 1;
					break;
				}
			}
			if(!failed)
			{
				b[bi][0]=i, b[bi][1]=j;
				bi++;
				if(!color)
				{
					if(bi > ans_b) ans_b = bi;
				}
				else
					if(bi > ans_w) ans_w = bi;
				solution(i,j,color);
				bi--;
			}
		}
	}
}
int main(void)
{
	register int i,j,k,m;
	scanf("%d", &n);
	for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d", &g[i][j]);

	// i,j 위치에 비숍을 놓을 경우
	// 영향이 가는 지점을 미리 저장
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(!g[i][j]) continue;
			for(k=0;k<4;k++)
			{
				int ni=i, nj=j;
				while((0<=ni&&ni<n)&&(0<=nj&&nj<n))
				{
					dp[i][j][ni][nj] = BISHOP;
					ni += di[k], nj += dj[k];
				}
			}
		}
	}

	bi=0;
	solution(0,0,0);
	bi=0;
	solution(0,1,1);
	printf("%d\n", ans_w+ans_b);
	return 0;
}