BOJ 9663번 N-Queen 문제 자바(java) 풀이
이 문제는 백트래킹 공부를 한다면 무조건 풀고가야 할 문제입니다.
이 문제를 풀어서 설명할 줄 안다면 백트래킹의 기본은 이해했다고 볼 수 있을것 같아요
백트래킹의 개념을 알고 구현할 줄 안다면 그리 어렵지 않은 문제이지만(난이도도 실버1)
모른다면 처음에 어떻게 접근해야할지 정말 막막한...ㅠㅠ
8중 for문을 돌려도 되려나??? 가능할지도 모르겠어요 ㅋㅋㅋㅋㅋ
문제이해
이 문제는 백트래킹을 이용해서 풀 수 있는 문제로 완전탐색을 통해 모두 찾아봐야 합니다
체스를 둘 줄 모르는 분들을 위해서 간략히 룰에 대해서 설명 드리겠습니다.
체스 말 중 퀸(Queen)은 상하좌우, 주대각선, 부대각선 방향 모두 이동할 수 있다.
전 방향으로 이동해서 모든 말 들을 공격할 수 있는 체스의 핵심 말이라 할 수 있습니다. (몇 칸이든 이동 가능)
n-queen 문제를 예를 들어서 설명드릴게요!!
아래와 같은 경우 처럼 놓을 수 없어요
1 x x x
x x x x
x x x x
x x x 1
예를 들어 4x4 체스 판 배열에 말이 두개가 위 처럼 놓여있다면
대각선 방향에 존재하므로 서로 공격할 수 있다.
즉 공격 할 수 없게 하기 위해서는 상하좌우, 대각선 어느 위치에든 말이 없어야 한다.
문제 풀이 및 설명
행이나 열을 기준으로 하나씩 놓으면서 backtracking을 통해 말들을 놓을 수 있습니다.
저는 행을 기준(?)으로 행에 하나씩 놓고 다음 행에 놓고.. 이런 식으로 하였습니다.
backtarcking이란??
우선 재귀 함수를 어느 정도 짜보셔야 이해가 가실 겁니다. stack에 대한 개념도요!!
재귀 함수의 기본적인 문제인 피보나치 문제도 풀어보시기 바립니다.
백준에도 피보나치 문제가 굉장히 많은데요. 풀어보시고 답안 코드는 여기를 참고하세요
재귀 함수 피보나치 문제
- 2742(피보나치 수)
- 2749(피보나치 수3)
- 10826(피보나치 수 4)
- 10875(피보나치 수 5)
백트래킹을 하는 이유는 이전 상태를 기억하고 다음 상태로 나아가기 위함 입니다.
예를 들어 4x4의 체스판을 예로 들어서 설명드릴게요
우선 처음에 1,1 부터 말을 두기 시작합니다
1 x x x
x x x x
x x x x
x x x x
다음 말을 다음 행의 왼쪽 끝 열부터 둡니다 (같은 행은 어차피 두면 안되니까)
그런데 2,1은 같은 열에 위치하므로 들 수 없고 2,2도 대각선에 위치해서 둘 수 없습니다.
그래서 2,4에 둡니다.
1 x x x
x x 1 x
x x x x
x x x x
다음 행에 둡니다. 이때도 3,1은 세로로 겹쳐서 안되고 3,2에 두면 2번째 줄의 말과 대각선에 겹치고
3,3은 2번째 말과 세로로 겹치고 3,4는 2번째 줄의 말과 대각선으로 겹칩니다. 그래서 3번째 줄에 말을 둘 수 없습니다.
즉 위 상태로 말을 둘 수 없기 때문에 이전의 상태로 돌아가서 다음 열에 두어야 합니다. 다음과 같이 말이죠
이전 상태로 돌아가기 위해서 그 전 상태의 context를 기억해야 합니다.
그래서 재귀를 통해 stack에 쌓아두고 이전 상태로 돌아가는 겁니다.
그러면 돌아가서 다음 열인 2,4에 말을 둘 수 있습니다( 2번째 체스 판 그림에서 3열까지 확인 했으므로 )
1 x x x
x x x 1
x x x x
x x x x
그러면 1,1에 체스말을 두었을 경우 모두 확인하고 1행에 말을 둘 때의 첫 함수 상태로 돌아가서 (1,2) 에 말을 두게 됩니다.
이제 이해가 되시나요??? 그래도 이해가 잘 안되신다면 직접 디버깅을 통해 함수의 stack 상태를 확인하면서
천천히 디버깅 해보시면 감이 오실 겁니다!!
backtracking과 dfs의 차이
백트래킹(backtrakcing)과 dfs는 비슷하지만 약간의 차이가 있습니다.
둘의 다른점은 backtracking으로 풀면 dfs로 풀었을때보다 더 적은 수를 탐색하게 됩니다.
왜냐하면 중간에 이 길이 가능한 길인지 먼저 검사를 하고 놓기 때문입니다.
이것을 가지치기한다라고 불렀던 것 같아요
promising funciton
이는 backtracking을 해나가기 전에 검사하는 함수입니다.
위에서 말한 가지치기를 위한 함수에요
이 함수를 통해 다음으로 나아가도 되는지 유무를 검사하여 계산해야할 경우의 수를 줄여갑니다
- 한 행에 하나 밖에 두지 않기 때문에 같은 열에 두려는지 확인한다. (배열의 value 값이 같은지 확인)
- 대각선으로 겹치는지 확인한다.
- 예를들어 1,2에 두었고 다음에 (2, 3)에 두려고 한다.
- 이때 행의 차이와 열의 차이가 1로 같기 때문에 같은 대각선 상에 있음을 알 수 있다.
퀸 배치
이 문제는 행의 어느 열에 두었냐만 알면 되므로 2차원 배열이 필요 없습니다.
물론 2차원 배열을 이용해서 구현도 가능합니다.
즉 cols[row] = col => (row, col)이 됩니다. 즉 그 위치에 퀸을 둔 것입니다.
이 방식은 다른 문제를 풀다가도 쓰이므로 기억해두시면 좋을 것 같습니다!!
자바 backtarcking 구현
보시면 dfs의 재귀적 호출 방법과 같습니다.
하지만 하나가 다르죠
isRightPosition(row,c)라는 promising function이 추가되어 있어요
이를 통해 다음 재귀를 통해 다음 행으로 나아갈 것인지 다음 열로 이동하여 놓을 것인지 확인합니다
이 형태를 외워두시고 isRightPosition이라는 promising 함수만 다른 함수로 문제에 맞게 바꿔 작성하시면 됩니다
static void backtracking(int row) {
if(row == n) {
cnt++;
return;
}
for(int c=0; c<n; c++) {
if(isRightPosition(row, c)) {
cols[row] = c;
backtracking(row+1);
}
}
}
n-queen 자바 코드
n-queen 자바 코드 github
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Main{
static int[] cols;
static int n;
static int cnt;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
cols = new int[n];
cnt = 0;
// 퀸 N 개를 서로 공격할 수 없게 놓는 경우의 수 구하기
// 퀸은 모든 방향으로 갈 수 있음
backtracking(0);
bw.write(cnt + "");
bw.flush();
br.close();
bw.close();
}
static void backtracking(int row) {
if(row == n) {
cnt++;
return;
}
for(int c=0; c<n; c++) {
if(isRightPosition(row, c)) {
cols[row] = c;
backtracking(row+1);
}
}
}
static boolean isRightPosition(int x, int y) {
boolean flag = true;
for(int i=0; i<x; i++){
if(cols[i] == y || Math.abs(x-i) == Math.abs(y - cols[i]))
return false;
}
return flag;
}
}