백준 9663: N-Queen
/ 17분 분량 / 문제 풀이
Gold IV 난이도의 N-Queen 문제를 C++로 풀이한 내용입니다. N x N 체스판에 N개의 퀸을 서로 공격할 수 없도록 놓는 문제입니다.
백준 9663: N-Queen
Gold IV 난이도의 N-Queen 문제를 C++로 풀이한 내용입니다. N x N 체스판에 N개의 퀸을 서로 공격할 수 없도록 놓는 문제입니다.
문제 소개
- 문제 번호: 9663
- 문제명: N-Queen
- 난이도 (티어): Gold IV
- 사용 언어: C++
- 실행 시간: 1588 ms
- 메모리: 2020 KB
- 문제 요약: N x N 크기의 체스판 위에 N개의 퀸을 배치할 때, 서로 같은 행, 같은 열, 또는 같은 대각선 상에 퀸이 놓이지 않도록 하는 모든 배치 방법의 수를 구하는 문제입니다.
접근 방법
N-Queen 문제는 재귀와 백트래킹을 이용한 깊이 우선 탐색(DFS)으로 해결할 수 있습니다. N이 최대 15까지 주어지므로, 모든 경우의 수를 탐색하는 완전 탐색은 시간 초과가 발생합니다. 따라서 퀸을 놓을 때마다 충돌하는 경우를 미리 확인하고 가지치기(pruning)하는 백트래킹 기법이 필수적입니다.
선택한 알고리즘/자료구조
- 깊이 우선 탐색 (DFS): 체스판의 각 행에 퀸을 하나씩 놓으면서 가능한 모든 경우를 탐색합니다.
- 백트래킹: 현재 위치에 퀸을 놓았을 때 이후의 탐색에서 충돌이 발생할 가능성이 있다면, 해당 위치에 퀸을 놓지 않고 이전 상태로 돌아갑니다.
- 불리언 배열 (boolean arrays):
usedCol: 현재 열에 퀸이 놓여 있는지 추적합니다.usedDiag1: '' 방향 대각선에 퀸이 놓여 있는지 추적합니다.usedDiag2: '/' 방향 대각선에 퀸이 놓여 있는지 추적합니다.
선택 이유
N-Queen 문제는 조합적 탐색 문제로, N이 증가함에 따라 경우의 수가 기하급수적으로 늘어납니다. DFS는 이러한 탐색 공간을 체계적으로 탐색하는 데 적합하며, 백트래킹은 불필요한 탐색을 줄여 시간 복잡도를 효율적으로 관리할 수 있게 해줍니다. 3가지 used 배열을 통해 퀸의 충돌 여부를 O(1) 시간에 판별할 수 있어, DFS 탐색 효율을 극대화할 수 있습니다.
풀이 과정
DFS 함수 정의 (
dfs(int row)):- 이 함수는
row번째 행에 퀸을 놓는 역할을 담당합니다. - 종료 조건:
row가 N과 같아지면, N개의 퀸을 모두 체스판에 성공적으로 배치한 것이므로 카운트(cnt)를 1 증가시키고 재귀를 종료합니다. - 탐색:
row번째 행에서 가능한 모든 열(col= 0부터 N-1까지)에 대해 퀸을 놓을 수 있는지 확인합니다.
- 이 함수는
충돌 확인:
- 각
col에 대해 퀸을 놓기 전에,usedCol[col],usedDiag1[d1],usedDiag2[d2]를 확인합니다. d1( '' 방향 대각선 인덱스):row - col + (N - 1)으로 계산됩니다.row - col값은 같은 '' 대각선 상의 모든 칸에서 일정하므로, 음수 인덱스를 방지하기 위해(N - 1)을 더해줍니다.d2( '/' 방향 대각선 인덱스):row + col로 계산됩니다.row + col값은 같은 '/' 대각선 상의 모든 칸에서 일정합니다.- 만약 세 조건 중 하나라도
true이면, 해당col에는 퀸을 놓을 수 없으므로continue를 통해 다음col을 탐색합니다.
- 각
퀸 배치 및 재귀 호출:
- 충돌이 없을 경우, 해당
col에 퀸을 놓는 것으로 간주하고usedCol[col],usedDiag1[d1],usedDiag2[d2]를true로 설정합니다. - 다음 행(
row + 1)에 퀸을 놓기 위해dfs(row + 1)을 호출합니다.
- 충돌이 없을 경우, 해당
백트래킹:
dfs(row + 1)호출이 반환되면, 현재col에 퀸을 놓았던 상태를 되돌려야 합니다. 이는 다른col에 대한 탐색을 위해usedCol[col],usedDiag1[d1],usedDiag2[d2]를 다시false로 설정하는 것으로 이루어집니다.
메인 함수:
N값을 입력받습니다.dfs(0)을 호출하여 0번째 행부터 퀸 배치를 시작합니다.- 최종적으로 계산된
cnt값을 출력합니다.
핵심 아이디어
- 열 및 대각선 충돌 관리: 3개의 boolean 배열을 사용하여 어떤 열과 대각선에 이미 퀸이 배치되었는지 효율적으로 관리합니다.
- 대각선 인덱스 계산:
row - col + (N-1)와row + col을 사용하여 각 대각선을 고유한 인덱스로 표현하고, 배열을 통해 O(1) 탐색을 가능하게 합니다. - DFS 기반 탐색: 재귀적으로 각 행에 퀸을 놓으며 탐색 공간을 체계적으로 탐색합니다.
- 백트래킹을 통한 가지치기: 더 이상 퀸을 놓을 수 없는 경우나 충돌이 발생하는 경우 즉시 탐색을 중단하고 이전 상태로 돌아가 불필요한 연산을 줄입니다.
주의할 점
- 대각선 인덱스 계산 시 음수 값이 발생하지 않도록 주의해야 합니다.
usedDiag1의 경우N-1을 더해 인덱스를 조정합니다. - N의 크기에 따라 가능한 대각선의 개수가 다르지만,
2*N - 1개 정도의 크기로 배열을 선언하면 N ≤ 15 범위에서는 충분합니다. 코드에서는 최대 N=15를 고려하여 약 30 크기의 배열을 사용했습니다. - 백트래킹 과정에서
used배열들을 정확히false로 되돌려야 합니다. 이를 생략하면 잘못된 결과가 나올 수 있습니다.
코드 설명
#include <bits/stdc++.h>
using namespace std;
int N;
int cnt = 0;
/*
usedCol[c]:
→ 열 c에 이미 퀸이 있냐?
→ 같은 col에 두 퀸 못 놓으니까 필요
*/
bool usedCol[15];
/*
usedDiag1[d]:
→ '\' 방향 대각선 체크용
→ 이 대각선의 수학적 정의:
row++, col++ 로 이동하면
row - col 값이 변하지 않는다
→ 즉, 같은 '\' 대각선 위의 모든 칸은
row - col 값이 동일하다
row - col 의 값 범위:
min: 0 - (N-1) = -(N-1)
max: (N-1) - 0 = +(N-1)
배열 인덱스는 음수가 안 되므로
+(N-1) 을 해서 전부 양수로 평행이동
→ 그래서:
d = row - col + (N-1)
가능한 값(대각선) 개수:
-(N-1) ~ +(N-1)
→ 총 2N - 1 개
→ N ≤ 15 이므로 최대 29개
→ 그래서 배열 크기 30 (여유)
*/
bool usedDiag1[30];
/*
usedDiag2[d]:
→ '/' 방향 대각선 체크용
→ 이 대각선의 수학적 정의:
row++, col-- 로 이동하면
row + col 값이 변하지 않는다
→ 즉, 같은 '/' 대각선 위의 모든 칸은
row + col 값이 동일하다
row + col 의 값 범위:
min: 0 + 0 = 0
max: (N-1) + (N-1) = 2N - 2
가능한 값(대각선) 개수:
0 ~ 2N - 2
→ 역시 총 2N - 1 개
→ 그래서 배열 크기 30
*/
bool usedDiag2[30];
/*
dfs(row):
→ row번째 행에 퀸 하나 놓는 함수
→ row 자체는 항상 하나씩 증가
→ 같은 row에는 어차피 하나만 두므로
row 충돌 체크는 필요 없음
*/
void dfs(int row) {
/*
종료 조건:
row == N 이면
row 0 ~ N-1 까지
모순 없이 다 놓았다는 뜻
→ 하나의 완전한 해
*/
if (row == N) {
cnt++;
return;
}
/*
현재 row에서
가능한 모든 col을 시도
→ 세계선 분기 (DFS 트리)
*/
for (int col = 0; col < N; col++) {
int d1 = row - col + (N - 1); // '\' 그 대각선의 고유한 상수값
int d2 = row + col; // '/' 그 대각선의 고유한 상수값
/*
세 조건 중 하나라도 true면: 영역 충돌
→ 같은 열이거나
→ 같은 '\' 대각선이거나
→ 같은 '/' 대각선
→ 퀸끼리 서로 공격 가능
우리는 "퀸이 어느 쪽으로 쏘는가"를 전혀 보지 않는다.
(오른쪽 위? 왼쪽 아래? 이런 물리적 방향은 버린다)
우리는 오직 이것만 본다:
→ "이 퀸이 어떤 '직선 족보'에 속해 있느냐"
체스판의 대각선은 딱 두 패밀리뿐이다:
1) 기울기 +1 계열: row - col = 상수 → '\' 패밀리
2) 기울기 -1 계열: row + col = 상수 → '/' 패밀리
각 퀸은 항상:
- '\' 직선 하나
- '/' 직선 하나
를 동시에 점유한다.
그리고 공격 판정은:
"같은 직선 위에 있느냐?" 만 본다.
서로를 향하느냐? 같은 방향으로 가느냐?
→ 전부 의미 없음.
직선은 방향이 아니라 '집합'이기 때문.
*/
if (usedCol[col] || usedDiag1[d1] || usedDiag2[d2])
continue;
/*
이 자리는 안전
→ 상태 공간에 "퀸 하나 놓음"
*/
usedCol[col] = true;
usedDiag1[d1] = true;
usedDiag2[d2] = true;
// 다음 row로 내려감
dfs(row + 1);
/*
백트래킹:
방금 선택은
다른 세계선 탐색 위해 되돌림
*/
usedCol[col] = false;
usedDiag1[d1] = false;
usedDiag2[d2] = false;
} // 여기까지 오면 실패
// => 갈 수 있는 자식이 하나도 없는 노드 : for 종료, dfs(row) 함수 끝
// => 이 노드는 탐색트리에서 리프(막힌 리프)
// => 더 내려갈 수 없으므로 현재 분기 종료
// 이 행에서 더이상 퀸을 둘 수가 없다
// => 이 경로로는 해에 도달하지 못한다
// => 부모 dfs로 돌아간다
// => 암묵적 return
}
int main() {
cin >> N;
dfs(0);
cout << cnt;
}
/*
========================
DFS 탐색 트리 예시 (N=4)
========================
각 노드 = dfs(row) 상태
각 간선 = col 선택
row = 0
|
|-- col 0
| |
| |-- row = 1
| | |-- col 2
| | | |
| | | |-- row = 2
| | | | (모든 col 충돌 → dead end)
| | |
| | |-- col 3
| | |
| | |-- row = 2
| | |-- col 1
| | |
| | |-- row = 3
| | (모든 col 충돌 → dead end)
|
|-- col 1
| |
| |-- row = 1
| |-- col 3
| |
| |-- row = 2
| |-- col 0
| |
| |-- row = 3
| |-- col 2
| |
| |-- row = 4 ★ 해 1
|
|-- col 2
| |
| |-- row = 1
| |-- col 0
| |
| |-- row = 2
| |-- col 3
| |
| |-- row = 3
| |-- col 1
| |
| |-- row = 4 ★ 해 2
|
|-- col 3
|
|-- row = 1
|-- col 0
| |
| |-- row = 2
| |-- col 2
| |
| |-- row = 3
| (dead end)
|
|-- col 1
|
|-- row = 2
(dead end)
총 해 개수: 2
(실제 4-Queen 정답과 일치)
========================
이 트리의 본질
========================
- 각 깊이 = row
- 각 분기 = col 선택
- 가지가 잘리는 지점 =
usedCol / usedDiag1 / usedDiag2 중 하나 충돌
즉 이 코드는:
"4^4 전부 보는 게 아니라,
충돌하는 세계선은 생성 즉시 우주 삭제"
하는 구조의 탐색기.
*/
복잡도 분석
- 시간 복잡도: O(N!)
- 이 문제는 이론적으로 N!의 복잡도를 가집니다. 각 행마다 N개의 열을 선택할 수 있고, N개의 행이 존재하므로 최악의 경우 N^N까지 탐색할 수 있습니다. 하지만 백트래킹을 통해 상당수의 탐색 경로가 잘려나가기 때문에 실제로는 N!에 가깝게 동작합니다. N ≤ 15에서는 이 정도 복잡도가 허용됩니다.
- 공간 복잡도: O(N)
- DFS 재귀 호출 스택의 깊이가 최대 N까지 갈 수 있습니다.
usedCol,usedDiag1,usedDiag2배열의 크기가 N에 비례하므로(최대 30), 공간 복잡도는 O(N)으로 볼 수 있습니다.
배운 점
N-Queen 문제는 백트래킹 알고리즘의 대표적인 예시입니다. 이 문제를 통해 다음과 같은 점을 배울 수 있었습니다.
- 백트래킹의 중요성: 완전 탐색으로는 해결하기 어려운 조합적 문제를 해결하기 위해 백트래킹이 얼마나 효율적인지 체감할 수 있었습니다. 상태 공간 트리를 그려보며 어떤 경우에 가지치기가 발생하는지 이해하는 것이 중요합니다.
- 상태 표현: 퀸의 충돌을 효과적으로 감지하기 위해 열과 두 종류의 대각선 상태를 boolean 배열로 관리하는 방법을 배웠습니다. 특히, 대각선을 수학적인 관계로 표현하고 인덱스화하는 아이디어가 인상 깊었습니다.
- DFS 활용: 재귀 함수를 사용하여 깊이 우선 탐색을 구현하는 방법을 다시 한번 익혔습니다. 재귀 호출의 종료 조건과 상태 변경, 그리고 백트래킹의 중요성을 깊이 이해할 수 있었습니다.
- 효율적인 제약 조건 확인: 퀸의 공격 범위를 단순히 시각적으로 판단하는 것이 아니라, 수학적 속성(행, 열, 대각선)을 이용하여 간결하고 빠르게 검증하는 방법을 배울 수 있었습니다.
이 문제는 다양한 탐색 문제에 백트래킹 기법을 적용하는 데 좋은 기반이 될 것이며, 복잡한 상태 공간을 효율적으로 탐색하는 능력을 키우는 데 도움이 되었습니다.