[백준] 1799번: 비숍

문제

[백준] 1799번: 비숍

분석

격자에 비숍을 놓을 수 있는지 없는지 정보가 주어질 때, 서로 잡을 수 없는 위치에 놓을 수 있는 최대 비숍 개수를 구하는 문제이다.

N이 최대 10이라 단순히 백트래킹을 했을 경우를 생각하면 최악의 경우 2^100 번 연산을 수행하게 되어 어마어마한 시간이 걸린다. (격자칸이 최대 100칸)

비숍은 다른 색의 체스칸에 놓인 것은 절대 잡지 못한다. 따라서 흑백으로 나누어 연산을 진행해서
2^50 + 2^50 으로 진행하면 훨씬 시간을 줄일 수 있다. 2^50은 여전히 크지만 가지치기를 하여 못 놓는 경우가 많아지기 때문에 통과할 수 있다. 이 문제는 흑백을 분리하지 않고 통으로 계산하는 경우를 거르기 위함으로 보인다.

지난번 격자에서 백트래킹에 숫자 하나로 위치를 계산한 것을 떠올려, pos로 몫과 나머지를 통해 x, y를 구했다.
color로 0과 1을 구분해 (x+y)%2와 같은지 체크를 하고 각각 백트래킹을 진행했다.
놓을 수 있는지 판별할 때는 대각선 위쪽 두 방향만 격자를 나갈 때까지 체크했다.

코드 상 $O(2 \times (2^{N^2/2} \times N))$가 시간 복잡도이지만, 실제로는 가지치기로 인해 더 줄게 된다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[][] grid;
	static int[] mx = new int[2];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		grid = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		backtracking(0, 0, 0);
		backtracking(0, 0, 1);
		System.out.println(mx[0] + mx[1]);
		br.close();
	}

	static void backtracking(int pos, int cnt, int color) {
		mx[color] = Math.max(mx[color], cnt);
		for (int i = pos; i < N * N; i++) {
			int x = i / N;
			int y = i % N;
			if ((x + y) % 2 == color && isPossible(x, y)) {
				grid[x][y] = 2;
				backtracking(i + 1, cnt + 1, color);
				grid[x][y] = 1;
			}
		}
	}

	static boolean in_range(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < N;
	}

	static boolean isPossible(int x, int y) {
		if (grid[x][y] != 1)
			return false;
		int x1 = x - 1, y1 = y - 1;
		while (in_range(x1, y1)) {
			if (grid[x1][y1] == 2)
				return false;
			x1 -= 1;
			y1 -= 1;
		}
		int x2 = x - 1, y2 = y + 1;
		while (in_range(x2, y2)) {
			if (grid[x2][y2] == 2)
				return false;
			x2 -= 1;
			y2 += 1;
		}
		return true;
	}

}