-
[BOJ - JAVA] 9663 - N-Queen (백트래킹) 본문
# 주소
https://www.acmicpc.net/problem/9663
# 문제
# 문제 해설 및 코드 리뷰
import java.util.*;
public class Main {
static int n;
static int arr[];
static int count = 0;
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n];
nqueen(0);
System.out.println(count);
}
public static void nqueen(int cnt){
if(cnt == n){
count++;
return;
}
for(int i = 0; i < n; i++){
arr[cnt] = i;
if(possibility(cnt)){
nqueen(cnt+1);
}
}
}
public static boolean possibility(int t){
for(int i = 0; i < t; i++){
if(arr[t] == arr[i]){
return false;
}
else if(Math.abs(t - i) == Math.abs(arr[t] - arr[i])){
return false;
}
}
return true;
}
}
체스를 잘 몰라서 룰을 좀 찾아야 했습니다.
그래서 다른 분의 블로그도 많이 참고를 했습니다.. ㅠㅠ
체스에서 퀸을 움직이게 할 수 있는 여러 칸들 중에서 절대 이동경로에 없는 경우의 수를 구하는 문제입니다.
문제에서는 8개의 퀸을 주었고 이 8개의 퀸을 적절히 배치하여, 서로 이동경로상에 없게끔 배치하면 됩니다.
따라서, 코딩을 먼저 한 번 보시겠습니다.
일단 n을 입력받고 arr를 n크기로 선언합니다.
그리고 nqueen(0)을 실행하는데, nqueen은 dfs로 사용할 것입니다.
dfs란 깊이 우선 탐색으로서, 여기선 그 중에서도 백트래킹 기법을 이용합니다.
만약 백트래킹이 무엇인지 모르신다면, 백트래킹은 "지나가다가 여기가 아니면 취소하고 뒤돌아가는" 의미로 이해하시면 좋겠습니다.
자. 백트래킹을 구현할 때는 dfs 구문 내에 cnt(놓을 수 있는 횟수) 가 n이 되는지. 만약 만족한다면 count를 증가시키고 return시킵니다.
그리고 그렇지 못할 경우 for문에서, arr의 현재 cnt를 i로 저장합니다. 그리고 그 cnt가 과연 어떤 값을 가질 수 있을지 모르잖아요?
그래서 possibility를 통해 검증을 합니다.
만약 이 메서드에 cnt를 넣어서 참이라면 재귀함수 nqueen에 (cnt+1)을 해줄테고 아니라면 for문의 i를 증가시킵니다.
자 무슨말일까요??
안와닿으시겠지만 이렇게 이해해 봅시다.
퀸 | - | - | - |
- | |||
- | |||
- |
0행0열에 퀸을 놓았습니다.
그럼 1열에 퀸을 두어야 할텐데, 어디에 두어야 할지 모르잖아요???
그래서 posibility를 통해 검증을 하는 것입니다.
지금 제일 먼저 들어갈 cnt값은 0입니다.
근데, 0은 arr[0]이 제일 먼저 선점해서 들어가 있는 상태이므로 cnt는 0을 생략하고 1을 검증할 것입니다.
그러나 arr[1] = 1이 되어버리면 possibility에서 두번째 else if문에서 대각선의 길이가 행의 값의 차이와 같아지므로(대각선에 있으므로) arr[1]은 0도 안되고 1도 안되니 건너 띄워집니다.
그럼 arr[1] 은 for문에 의해 그 다음 숫자가 되는 것입니다. 자, i가 2일땐 어떻나요?
그럼 표가 이렇게 됩니다.
퀸 | - | - | - |
- | - | - | |
- | 퀸 | - | - |
- | - | - |
이렇게 그려질 것입니다.
근데 이렇게 배치를 해버리면 n개의 체스를 놓을 수 없습니다.
2열에 어떤 체스도 놓을 수 없기 때문입니다.
따라서 0행0열에 퀸을 놓으면 안되게 됩니다.
그러므로 다시 실행했던 재귀함수가 돌아오면서(백트래킹 되면서) 이번엔 1행 0열에 퀸을 놓습니다.
- | - | - | - |
퀸 | - | - | - |
- | |||
- |
이런식으로 말이지요.
그럼 1열엔 어디에 퀸을 둘 수 있나요?
- | - | - | - |
퀸 | - | - | - |
- | - | ||
- | 퀸 | - | - |
이렇게 되겠지요. 더 나아가서
- | - | 퀸 | - |
퀸 | - | - | - |
- | - | - | 퀸 |
- | 퀸 | - | - |
이렇게 놓을 수도 있을 것입니다.
이것이 첫번째 count가 됩니다.
그리고 다시 return하여 이번엔 0행 3열에 퀸을 놓습니다.
그럼 다음과 같이 전개될 것입니다.
- | 퀸 | - | - |
- | - | - | 퀸 |
퀸 | - | - | - |
- | - | 퀸 | - |
그럼 0행 3열에 퀸을 두면 어떻게 될까요?
- | 퀸 | - | - |
- | - | - | 퀸 |
- | - | 퀸 | - |
퀸 | - | - | - |
아마 이렇게 전개가 되어야 하지만, 3행 1열의 퀸과 2행 2열의 퀸이 대각선상에 있기 때문에 possibility에서 false판정을 받고, count에 포함이 되지 않을 것입니다.
이해가 가셨나요?
대각선상에 있을 땐 Math.abs(t-i) == Math.abs(arr[t] - arr[i]) 구문을 잘 기억하면 좋겠습니다.
감사합니다.
'백준 문제 풀이' 카테고리의 다른 글
[BOJ - JAVA] 1707 - 이분 그래프 (BFS) (0) | 2021.12.20 |
---|---|
[BOJ - JAVA] - 구간 합 구하기4 (세그먼트 트리) (0) | 2021.12.19 |
[BOJ - JAVA] 14888 - 연산자 끼워넣기 (백트래킹) (0) | 2021.12.17 |
[BOJ - JAVA] 1987 - 알파벳 (DFS) (0) | 2021.12.15 |
[BOJ - JAVA] 케빈 베이커의 6단계 법칙 (0) | 2021.12.13 |