boj 1799 : 비숍

 

boj 1799 : 비숍

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

 

 

기본적인 DFS + 커팅 방법을 사용하여 해결할 수 있다.

백준 9663번 N-Queen와 유사하다.

 

0. DFS + 커팅방법

지정한 y, x에 놓을 수 있는지 판단하기 위해 (y-1,x-1), (y-2,x-2) ... 를 모두 확인하면 판단을 위해 O(N)의 복잡도가 추가로 소모된다. 판단은 O(1)로 끝내야 한다. true나 false를 담은 check배열을 이용하여 한 번의 접근으로 말을 놓을 수 있는지 판단하도록 모델링해야 한다.

 

이후, DFS + 커팅 방법을 보완하기 위해 크게 2가지 기법을 추가로 사용하였다.

1. 좌표변환

위와 같이 좌표 변환을 끝내 놓으면, N-Queens문제보다 더 쉬운 N-Rooks 문제로 바뀌게 된다.

좌표변환에는 (y', x') = (y+x, n-1-y+x) 와 같은 적당한 변환식을 이용한다.

구현 편의상 좌표변환을 하였으나, 변환하지않고 Diagonal Check배열을 만드는 방법도 있다.

2. 흑백분리

체스판을 곰곰히 살펴보면, 흑색 발판에 놓인 비숍은 백색 발판에 놓인 말을 절대 잡을 수 없다.

즉, DFS수행시 흑색발판 따로, 백색발판 따로 DFS를 수행해서 합치면 된다는 것을 의미한다.

시간복잡도가 N^N에 달하여 시간초과 나던 것을 (N/2)^(N/2) 수준으로 줄여 시간초과를 해소할 수 있다.