Baekjoon(백준) 9663번 - N-Queen
백준 사이트의 9663번.
문제 제목 : N-Queen
백준 9663
워낙 유명한 문제이고 이미 풀이가 많이 알려진 대표적인 문제이다보니 빠르게 넘어가겠다.
문제 해석
매우매우 유명한 N-Queen 문제 그대로이다.
풀이 전략
recursive function을 활용한 dfs search와 backtracking 을 이용하는 대표적인 문제이다. 이차원 array 상에서 queen 위치를 하나하나 바꿔가면서 탐색하면 너무 경우의 수가 많기 때문에 답이 없다. 어차피 하나의 row에는 하나의 queen 만 들어갈 수 있기 때문에 각 row에서 queen 위치가 어디있는지 저장하는 일차원 array를 이용하면 된다. 즉, 각 row마다 queen의 위치를 바꿔가면서 dfs 로 탐색하고 매번 해당 row의 해당 column 위치에서 대각선 방향이나 같은 column 에 이미 queen을 놓지는 않았는지 check 해주면 된다.
어차피 문제에서 시간 제한이 10초이고 $N < 15$이기 때문에 매번 for문을 돌려가며 이전에 놓은 queen과 서로 공격할 수 있는 위치에 있는지 체크를 해도 되지만, 나는 이 check를 좀 더 빨리 할 수 없을까 고민해보았다. 매번 queen을 놓을 때마다 해당 queen에 의해 못 쓰게 되는 column을 체크하는 1-dim array 하나, 대각선 방향 (diagonal) 으로 못 쓰게 되는 위치를 체크하는 2-dim array 하나를 만들어서 둘 다 만족할 때만 현재 row에 해당 column에 queen을 놓을 수 있도록 했다. 이 2개의 array는 recursive function을 호출하기 전에 값을 설정하고, 함수가 호출된 후에는 다시 원래대로 돌려놓아야 한다. 다음과 같이 말이다.
set_impossible(1, cur_row, i);
queen_dfs(cur_row + 1);
set_impossible(0, cur_row, i);
diagonal 방향을 체크하는 2-dim array의 경우 어떤 위치가 queen을 놓을 수 없는 자리라고 체크되어 있으면 꼭 현재 queen에 의해 못 쓰게 되는게 아니라 위에 이미 있는 queen에 의해 못 쓰게 된 것일 수 있다. 즉, true/false로만 하면 위의 코드에서 마지막 줄에 다시 원상태로 복구하는 과정에서 이미 위에 있는 queen에 의한 영향을 무시해버릴 수 있다. 따라서, diagonal 방향을 체크하는 2-dim array는 0인 경우는 queen을 놓을 수 있다는 의미이고, 양수인 경우는 queen을 놓을 수 없다는 의미로 설정했다. 그러면 어떤 queen의 위치에 의해 못 쓰게 되는 diagonal 방향의 자리를 체크하거나 원상태로 복구할 때 그 2-dim array는 값을 +1 하거나 -1 하면 된다. 그러면 이미 이전에 놓은 queen의 위치에 의한 영향도 모두 고려할 수 있는 것이다.
구현
구현은 뭐….뻔하다. 위에 설명한 대로 구현하면 된다.
사실 위에서 2개의 array를 통해 queen의 위치에 의해 못 쓰는 자리를 체크한다고 했는데, for문으로 매번 일일이 체크하는 것과 별 차이는 없는 것 같다. 그래도 사용한 column을 체크하는 1-dim array는 for문으로 체크하는 것보다는 확실히 시간을 줄여줄 것 같기는 하나 diagonal 방향을 체크하는 것을 for문으로 해도 상관없을 것 같다.
자세한 solution code는 github에 있다. 사실 내가 작성한 코드보다 훨씬 깔끔한 코드가 인터넷에 널려있다. 그래서 이번 코드는 이렇게도 구현할 수 있구나 하는 참고용이고, 정석적이고 깔끔한 코드는 인터넷을 참고하라.
Leave a comment