이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Gold V에 해당하는 문제인 9663번 : N-Queen을 풀이해보도록 하겠습니다.
+ Solved.ac 기준 Gold 난이도 문제에 도달했습니다. Silver 난이도 문제에서는 O(N log N) 정렬, 이진탐색, 큐, 스택, DFS와 BFS, 브루트포스 정도를 다루었는데 Gold 난이도에서는 어떤 알고리즘을 다룰지 모르겠습니다. 미리 문제들을 살펴본 바로는 백트래킹 정도를 다루는 것으로 보입니다. 아무튼 Gold 문제들도 이어서 풀이하겠습니다.
+ Gold 난이도 문제부터는 한 포스트에 한 개씩만 풀이를 작성하도록 하겠습니다.
이는 풀이의 길이가 길어지고 다뤄야 할 내용이 많기 때문입니다.
9663번 : N-Queen
N × N 크기의 체스판에 퀸 N개가 서로 공격할 수 없게 배치될 수 있는 경우의 수를 구하는 문제입니다.
이 문제의 경우 제한 시간이 10초로, 시간이 오래 걸려도 해를 구할 수만 있으면 많은 경우의 수를 계산하는 것을 허용하는 문제입니다.
답이 정해져 있는 문제라서 정해진 해만 출력해도 되지만, 여기서는 백트래킹을 활용하여 문제를 풀이해보도록 하겠습니다.
백트래킹이란 DFS나 BFS와 같은 단순 탐색과 달리, 조건에 부합하지 않는 부분에 도달하면 이전 분기점으로 되돌아가 다른 부분을 탐색을 시작하는 형태의 알고리즘입니다.
안 되는 수도 모두 계산하기보다 빠르게 제외하고 계산해주는 것이 시간 효율면에서 훨씬 뛰어나므로 백트래킹을 구현할 수 있다면 사용하는 편이 시간적으로 유리합니다.
#include<stdio.h>
int N, count = 0, queen[20], check;
int abs(int a) { return a>=0?a:-a; }
void search(int num) {
if(num == N+1) count++;
for(int i=1; i<=N; i++) {
queen[num] = i;
check = 1;
for(int j=1; j<num; j++) if(i == queen[j] || abs(i-queen[j]) == num-j) check = 0;
if(check) search(num+1);
}
}
int main() {
scanf("%d", &N);
search(1);
printf("%d", count);
}
예상 외로 입력 범위 중 가장 큰 값인 N=14를 대입했을 때 10초가 넘어가는 경우가 많았습니다.
구조체 또는 2차원 배열을 이용하여 board를 구현하려고 했으나, 시간을 아껴야하므로 조건을 이용해 코드를 단축시켰습니다.
우선 N-queen 문제에서 N개의 queen은 각각 하나의 행에 1개씩, 하나의 열에 1개씩 배치되므로 1행부터 N행까지 늘려가며 한 줄에 퀸을 1개씩 배치하면서 조건에 맞는지 확인하는 방법을 선택했습니다.
이렇게 될 경우 우선 행에 대한 선택은 사라지기 때문에 열과 대각선만 고려하므로 계산 시간이 훨씬 줄어들게 됩니다.
열의 경우 i와 queen[j]가 일치하는지만 확인하면 되고, 대각선은 x좌표끼리와 y좌표끼리를 빼서 그 값이 같은지로 확인할 수 있습니다.
전체적으로는 재귀함수를 이용하여 조건에 부합하는 경우에 한해서는 끝까지 탐색을 수행하고, N번째 행까지 배치가 성공적으로 이루어지는 경우 경우의 수를 하나 발견한 것으로 간주하여 count를 1 증가시켰습니다.
출력부를 작성해서 위와 같이 입력받은 N에 대한 경우의 수들을 출력해보면 코드가 제대로 작동하는 것을 확인할 수 있습니다. (위의 예시는 N=9인 상황)
#include<stdio.h>
int N, count = 0, queen[20], check, board[10][20][20], board_count = 1;
int abs(int a) { return a>=0?a:-a; }
void search(int num) {
if(num == N+1) {
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
if(j == queen[i]) board[board_count][i][j] = 1;
else board[board_count][i][j] = 0;
}
board_count++;
if(board_count == 10) {
for(int i=1; i<=N; i++) {
for(int j=1; j<=9; j++) {
for(int k=1; k<=N; k++) {
if(board[j][i][k]) printf("■");
else printf("□");
}
printf(" ");
}
printf("\n");
}
printf("\n");
board_count = 1;
}
count++;
}
for(int i=1; i<=N; i++) {
queen[num] = i;
check = 1;
for(int j=1; j<num; j++) if(i == queen[j] || abs(i-queen[j]) == num-j) check = 0;
if(check) search(num+1);
}
}
int main() {
scanf("%d", &N);
search(1);
printf("\n\n%d", count);
}
위의 접은 글에 코드를 첨부하니 혹시 활용하실 분들은 활용하셔도 됩니다.