[Java] 백준(골드-4) 9663번 - N-Queen
문제 풀이
이 문제는 백트래킹 유형의 대표 문제 중 하나이다.
아이디어 도출
이 문제에서는 아래 두가지를 유심히 살펴봐야 한다.
- 재귀함수를 어떻게 호출할까?
- 퀸을 놓을 수 있는지 어떻게 확인할까?
예시를 살펴보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
// N = 4일 때 경우의 수는 2가지
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
=> [2, 0, 3, 1]
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
=> [1, 3, 0, 2]
잘 보면 각 원소의 값을 행이라고 하고, 각 원소의 인덱스를 열이라고 하면 1차원 배열로 표현할 수 있다는 것을 알 수 있다.
위 예시의 첫번째 경우를 보면 [2, 0, 3, 1] 으로 원소의 값을 행, 인덱스를 열이라 생각하면 이해하기 쉽다.
재귀 호출 아이디어
그러면 재귀호출을 어떻게 해야할지 어느정도 그림이 그려진다.
첫 번째 열부터 퀸을 놓을 수 있는 위치라면 퀸을 놓아가면서 재귀호출을 하며 마지막 열까지 채웠을 때 N개의 퀸을 놓았으면 재귀 호출을 종료하면 된다.
퀸 검증 아이디어
재귀 호출 중 맵의 위치를 탐색해가며 현재 위치에 퀸을 놓을 수 있는지 어떻게 알 수 있을까? 다음 2가지 조건을 고려해야 한다.
- 해당 열, 같은 행에 다른 퀸이 놓여있을 경우, 해당 열의 행과 i열의 행이 일치할 경우 같은 행에 놓여있다는 의미이다.
- 대각선상에 다른 퀸이 놓여있을 경우, 행의 차와 열의 차가 같다면 대각선에 놓여있다는 의미이다.
위 2가지 조건 중 하나라도 걸린다면 현재 위치에 퀸을 놓지 못한다고 보면 된다.
자 위 내용들을 통해 정리한 문제 풀이 아이디어를 보자.
- 0번째 열부터 DFS를 호출해가며 퀸을 놓을 수 있는 위치인지 확인하여 퀸을 놓는다.
- 퀸을 놓을 수 있는 위치인지 확인할 때, 현재 열의 다른 행에 퀸이 이미 놓여있는지, 현재 위치 기준 대각선 상에 이미 퀸이 놓여있는지를 검사한다.
- 위 과정을 반복하며 N-1번째 열까지 탐색했을 때 N개의 퀸을 놓았다면 경우의 수의 카운트를 1 증가시키고 재귀를 종료한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.io.*;
import java.util.*;
class Main {
// 퀸이 서로 공격할 수 없도록 배치하는 모든 경우의 수를 구해야 한다.
// 게임판의 크기
static int N;
// 퀸을 놓을 배열
static int[] map;
// 경우의 수를 담을 변수
static int result;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
N = Integer.parseInt(br.readLine());
map = new int[N];
// 재귀함수 호출
dfs(0);
bw.write(result + "\n");
}
}
public static void dfs(int depth) {
// 깊이가 N이 되면 즉 행을 다 채우면 카운트 1 증가시키고 재귀 종료
if(depth == N) {
result++;
return;
}
// 1부터 N까지의 열을 탐색하며 i번째 행에 퀸을 놓는다.
for(int i=0; i<N; i++) {
// i열 depth행에 퀸을 놓는다.
map[depth] = i;
// 현재 열에서 i번째 행에 퀸을 놓을 수 있는지 확인하여 재귀 호출한다.
if(checkQueen(depth)) {
dfs(depth+1);
}
}
}
// 현재 위치가 퀸을 놓을 수 있는지 확인할 함수
public static boolean checkQueen(int col) {
for(int i=0; i<col; i++) {
// 해당 열의 행과 i열의 행이 일치할 경우
// 즉, 같은 행에 퀸이 놓여있을 경우는 퀸을 놓을 수 없기에 false
if(map[col] == map[i]) {
return false;
}
// 대각선 상에 퀸이 놓여있을 경우 불가하기에 false
// 열의 차와 행의 차가 같은 경우는 대각선에 놓여 있다는 뜻이다.
// col - i: 열의 차
// map[col] - map[i]: 행의 차
else if(Math.abs(col - i) == Math.abs(map[col] - map[i])) {
return false;
}
}
return true;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.