[Java] 백준 1799번 : 비숍

1. 문제

https://www.acmicpc.net/problem/1799

1799번: 비숍

 

 

 

2. 풀이과정

경우의 수 문제에 대각선의 특징을 이용하는 아이디어가 필요한 문제다.

 

우선, 모든 경우의 수를 고려하면 시간 복잡도는 O(2^(N*N))이고, 최대 2^100이므로 시간 초과가 난다.

x+y가 짝수인 집단과 홀수인 집단을 나눈다. 이들은 서로 절대 같은 대각선 상에 있을 수 없기 때문에, 독립적으로 계산한 후 결과들을 더해주면 되는 것이다. 나눠보면, 체크보드처럼 그려지는 것을 확인할 수 있다. 체크보드로 대각선을 확인해보자.

 

 

이렇게 집단을 나누면, 시간 복잡도는 O(2^(N/2*N/2)로 훨씬 효율적이다.

+) 같은 대각선에 1개 이상의 비숍이 있으면 안되므로, 대각선을 기준으로 방문 배열을 사용하여 구현했다.

 

처음엔, 전체 경우의 수를 고려해 시간 초과가 났다. 여러 시도 끝에, 질문에 있는 코드를 봤다. 대각선의 특징을 또 하나 배웠다.

import java.io.*;
import java.util.*;

public class Main {
	static int N, map[][];
	static int FIN, r, BoolLen;
	
	public static void go(boolean[] first, boolean[] second, int index, int cnt, int op) {
		if(index >= FIN) {
			r = Math.max(r, cnt);
			return;
		}
		int x = index/N;
		int y = index%N;
		//놓을 수 있다면
		if((x+y)%2==op && map[x][y]==1 && !first[x+y] && !second[(x-y+BoolLen)%BoolLen]) {
			//놓기
			first[x+y] = true;
			second[(x-y+BoolLen)%BoolLen] = true;
			go(first, second, index+1, cnt+1, op);
			//안 놓기
			first[x+y] = false;
			second[(x-y+BoolLen)%BoolLen] = false;
		}
		go(first, second, index+1, cnt, op);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		FIN = N*N;
		BoolLen = N*2;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int ans = 0;
		for(int i=0; i<2; i++) {
			go(new boolean[BoolLen], new boolean[BoolLen], i, 0, i);
			ans+=r;
			r = 0;
		}
		System.out.println(ans);
	}
}