![[백준,BOJ 9663] N-Queen (JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fuc1w4%2FbtqzUPcnmPY%2F1oO3G8Vjbk5B6lx4Rz9Juk%2Fimg.png)
글을 쓰기에 앞서 블로그 개설 후 방문자 수가 늘었다. ㅎㅎㅎ 그냥 개인 기록용 블로그로 쓰고 있는 거여서 방문자 수는 별로 신경 안 쓰고 있는데, 사람들이 찾아와 준다는 게 신기했다. 물론 글이 유익했는지는 모르겠지만.. 그래도 그중에는 도움을 받아가는 분이 있다고 믿고 싶다. ㅎㅎ
문제를 보자!
-내 생각
백 트래킹 알고리즘 중 가장 유명한 문제라는데 확실히 검색해보면 다른 많은 분들이 관련해서 글들을 많이 올리신 것 같다. 하지만 문제 자체는 쉽지 않다고 생각한다.. 실제로 이 문제를 풀기 위해서 3일을 소요했으니..(여러 개인 사정으로 자세히 고민해보지는 못했지만 ㅎㅎ)
우선 문제 자체는 어렵지 않다. 체스의 퀸을 활용한 문제인데, 체스의 룰에 대해서는 이전부터 알고 있었기 때문에 퀸이 상하 대각선으로 이동이 가능하다는 것을 인지하고 풀었는데, 도저히 풀 수가 없었다. 그래서 가능한 곳까지 구현 후 다른 분들의 블로그를 탐방했고, 거기서 많은 힌트들을 얻을 수 있었다.
-해법
첫 시도는 여태까지 풀었던 DFS문제뿐만 아니라 BFS문제에서는 항상 방문 배열을 사용했기 때문에 2차원 배열 형태의 체스판을 만들어 놓은 후 특정 지점에 퀸을 배치했을 때 해당 퀸이 이동 가능한 경로를 방문 배열에 표시해 놓고 표시되지 않은 공간을 넘겨주면서 재귀 호출을 생각했었는데, 이 경우에는 하나의 퀸을 배치 후 다음 퀸을 배치했을 때 그다음 퀸을 놓지 못한다면 이전의 놓은 퀸이 표시해 놓은 방문 배열을 원래대로 돌려야 해서 뭔가 잘못 접근하고 있다고 생각이 들었다.
두 번째 시도는 다른 분들의 블로그를 슬쩍 보고 0열의 행들을 기준으로 배치해가면서 경우를 따져보라는 글을 보고 0행 0열부터 1행 0열, 2행 0열... 식으로 갔는데 바보같이 열은 고정해놓고 행만을 바꿔서 또 한참을 삽질했다. 그러다 아래의 사진을 보게 되었는데
사진을 보면 4X4 체스판을 기준으로 경우의 수가 2개 존재한다는 것을 알 수 있었고, 열을 하나 고정 후 행을 모두 탐색하고 다음 열을 고정하고 모든 행을 탐색하고... 와 같은 알고리즘을 알 수 있었다.
위의 방식을 알게 된 후 마지막 삽질은 하나의 퀸을 기준으로 다음 퀸이 놓을 수 있는 공간을 배제하는 과정에서 앞선 퀸의 행과 앞선 퀸의 1칸 앞의 대각선들만을 배제했다... 이 경우 4X4의 체스판에서는 2의 경우의 수가 잘 나왔는데 8X8의 체스판에서 5264(?)라는 경우의 수가 나와서 이 부분에서도 한참을 고민했다. 그러다 8X8의 체스판을 그려보고 하나의 경우의 수를 체스판에 그려봤더니 6행 0열의 퀸이 놓인 경우 0행 6열의 퀸이 놓아지는 것을 알 수 있었다. 즉 6행 0열의 퀸의 대각선 범위에 0행 6열이 걸리는 것이다. 이런 현상이 발생되는 이유는 다음 퀸의 위치를 정하는 과정에서 특정 행을 배제해야 하는데 위에 언급했듯이 하나의 퀸을 기준으로 1칸 앞의 대각선만을 배제해버렸기 때문이었다... 결과적으로 퀸 하나를 기준으로 해당 퀸이 속한 행, 해당 퀸의 범위인 상하 대각선을 고려해주어야 한다.
이러한 삽질을 거친 후 조건을 수정해주었더니 이번엔 시간 초과가 발생한다... 체스판의 범위 최댓값인 14를 입력해보면 실제로 10초 이상이 걸리게 된다. 여기서 또 막혀서 다른 분들의 블로그를 탐색한 결과 하나의 퀸의 대각선에 속하는 조건을 Math.abs()를 이용해서 1개의 수식으로 작성한 것이었다. 여기서도 많이 고민했다..
어쨌든 위의 과정은 나의 삽질 과정이며 풀이는 코드를 보면서 확인해 보자.
import java.util.*;
class queen{ // 퀸의 클래스
int x; // 해당 퀸이 가지는 행 좌표
int y; // 해당 퀸이 가지는 열 좌표
int col[]; // 해당 퀸까지의 퀸들이 가지는 '열' 값
public queen(int x,int y,int[] col ) {
this.x=x;
this.y=y;
this.col = col;
}
}
public class Main {
static int n;
static int queen[]; // 퀸의 배열 , n의 개수에 따라 생성
static int g =0; // 경우의 수 카운트 변수
static void dfs(queen q) { // 퀸 전달
q.col[q.y] = q.x; // 해당 퀸에 저장 된 행 값인 x를 퀸 배열에 열 인덱스(y)에 저장
// 즉, 최초 실행 시 (0,0)에 첫 번째 퀸이 위치되고 x,y값을 행,열값으로 가지고
// col값을 퀸 배열로 가진다.
// 퀸 배열은 queen[0] = 0이 저장된 상태
if(q.y==n-1) { // 재귀호출 종료 부, 마지막 열까지 도달 시
g++; // 경우의 수 증가
return;
}
for(int i=0;i<n;i++) { // 열 증가 반복문, main()에는 행 증가 반복문이 있다.
q.col[q.y+1] = i; // 하나의 열에 퀸을 찾으면 다음 열로 이동하기 때문에
// 다음 퀸의 행값을 찾는 과정으로 i를 하나씩 넣어본다.
if(check(q)==true) { // 앞서 넣어본 i값이 이전 퀸들의 범위와 겹치는지 확인하기 위해
// check메소드를 호출한다.
dfs(new queen(i,(q.y+1),q.col));
q.col[q.y+1] = Integer.MAX_VALUE;
}
}
}
static boolean check(queen q) { // 전달받은 퀸 객체에는 현재 퀸 자신의 위치 정보(q.x,q.y)와
// 자신의 다음 퀸의 위치정보가 담긴 퀸 배열(q.col)이 있다.
for(int i=0;i<=q.y;i++) { // 현재까지 배치 된, dfs메소드에서 배치한 다음 퀸 까지를 탐색한다.
// 즉 퀸들의 범위에 겹치는지 확인하는 과정
if(q.col[i]==q.col[q.y+1]) return false; // 같은 행 불가
//dfs메소드에서 저장 된 i가 현재까지 저장 된
//퀸들과 같은 행을 가지는건 있을 수 없다.
//핵심인 퀸들의 대각선을 찾는 조건
//이는 예를 들어 설명해보면
// 예를들어 초기 상태에서 현재까지 q 객체에는 queen[0] =0, queen[1] =0의 위치정보를 가지고 있다.
// i는 queen의 인덱스 값을 의미하며, 0번 열에 위치한 퀸과 1번 열에 위치한 퀸의 열 차이는 '1'이다.
// 0번열의 0번행에 위치한 퀸과 1번열의 0번 행에 위치한 퀸의 행 차이는 '1'이다.
// 즉 dfs메소드에 의해서 열의 차이는 1로 고정이므로, 행의 차이가 1이나는 행은 다음 퀸의 행이 될 수 없는 것이다.
// 첫 번째 퀸의 행이 0이므로 1번행은 두 번째 퀸의 행이 될 수 없다.
// 또 다른 예를 들어보자. 현재까지 q 객체에는 queen[0] =1, queen[1] =0의 위치정보를 가지고 있다.
// 앞선 경우와 마찬가지로 열의 차이는 1로 고정이 되어있다. 그렇다면 첫 번째 퀸의 행값인 1과 빼기를 했을 때
// 차이가 1이 나는 행은 두 번째 퀸이 될 수 없다. 즉, 0번 행과 2번행은 다음 행의 후보에서 제외한다.
// 마지막 예시를 들어보자. 현재까지 q 객체에는 queen[0] =0, queen[1] =3의 위치정보를 가지고 있다.
// 0번 열과 1번 열의 퀸의 위치는 이미 찾았다. 다음 2번 열의 퀸의 위치를 찾아보자.
// q.y+1값은 2가 될 것이므로, (q.y+1) -i는 2-0 =2, 2-1,1 이 된다.
// 그렇다면, queen[2] - queen[0]이 2인 2번 행은 제외된다. 그리고 queen[2] - queen[1]이 1인 2번행이 제외된다.
// 마지막으로 각 퀸들이 속한 행 역시 제외되므로 최종적으로 0번, 2번, 3번 행이 제외되고 1번행이 2번열의 행값이 되는 것이다.
if( Math.abs((q.y+1)-i)==Math.abs(q.col[i]-q.col[q.y+1])) return false;
}
return true; //모든 경우를 통과하면 다음 행에 위치 할 수 있다.
}
public static void main(String[] args) { // 여기부터 봐주세용
Scanner sc= new Scanner(System.in);
n = sc.nextInt();
queen = new int[n]; // 퀸 생성 4x4의 체스판의 경우 4개의 퀸 배열 생성
// 퀸은 기본적으로 인덱스가 '열', 값이 '행'이 된다.
// 즉, queen[0] = 1의 경우 0번 열, 1번 행에 퀸이 위치한다는 뜻
// 자신을 포함한 이전까지 퀸의 위치정보를 저장한다.
for(int i=0;i<n;i++) { // 사진에서 확인할 수 있듯이 열을 고정하고 행을 증가하는 반복문
dfs(new queen(i,0,queen)); // 퀸의 배열과 함께 퀸을 하나 생성
// 첫 실행 시 이전에 배치한 퀸이 없기 때문에
// 퀸의 배열은 비어있다.
}
System.out.println(g); // 경우의 수 출력
}
}
잘 설명해보려고 했는데 글을 보는 분들이 이해가 될지 모르겠다. 솔직히 자기 코드는 자기가 제일 잘 알기 때문에 아무리 글로 설명해도 이해하기는 힘들다고 생각한다. 혹시라도 궁금한 점이 있다면 댓글 부탁드립니다!
이전에 오래 걸려서 푼 것이 무색하게 1시간 정도 고민하고 풀 수 있었다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
class Main {
static BufferedReader br;
static BufferedWriter bw;
static int n,ans=0;
// 배치된 퀸의 이동반경에 걸리는지 확인하는 메소드
static boolean isPossible(int[] check,int x,int y) {
// 0번 열부터 자신 이전의 열까지 데이터를 탐색해야 한다.
for(int i=1;i<=y;i++) {
// 이전열의 퀸의 행과 현재 열의 전달받은 행이 겹치면 배치할 수 없으므로 false
if(check[y-i] == x) return false;
// |현재 열의 행 - 이전 열의 행| == |현재 열 - 이전 열| 인 경우
// 이전 행, 열에 위치한 퀸의 대각선 범위에 포함되는 경우이므로 false
if(Math.abs(x-check[y-i]) == Math.abs(y-(y-i))) return false;
}
// 그 외는 고려할 필요가 없으므로 배치할 수 있다.
return true;
}
// DFS 메소드
static void dfs(int v,int[] check) {
// 마지막 열의 배치를 마치고 증가하면 check.length == v이 되므로 종료조건
// 마지막 열까지 배치를 완료했으므로 하나의 경우의 수가 발생한 것이다.
if(v == check.length) {
ans++;
return;
}
// 전달받는 v는 열, 아래 반복문은 고정된 열에서 행을 탐색한다.
for(int i=0;i<n;i++) {
// v가 0번 째 열
// 즉 처음 퀸을 배치하는 경우는 다른 퀸이 없기 때문에 차례대로 배치하면된다.
if(v == 0) {
check[v] = i; // check[0번 열] = 0번 행, 1번 행, 2번 행... 순서대로 들어간다.
dfs(v+1,check); // 0번 열이 정해지면 1번열을 DFS 탐색 수행
}else { // 0번 열이 아닌 나머지 열의 경우는 이전에 배치한 퀸의 범위를 고려해야 한다.
// 이전 퀸의 범위를 탐색하는 메소드
if(isPossible(check,i,v)) {
check[v] = i; // 배치가 가능한 경우 값을 넣어준다.
dfs(v+1,check); // 다음 열을 대상으로 DFS 탐색 수행
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
// check[열] = 행 방식으로 필자는 가정했다.
int check[] = new int[n];
dfs(0,check);
bw.write(String.valueOf(ans));
bw.flush();
bw.close();
br.close();
}
}풀면서 어려웠던 부분은
첫 째, 체스판을 check [행] = 열 or check [열] = 행으로 1차원 배열로 표기할 수 있다.
둘째, |현재 행 - 이전 행| == |현재 열 - 이전 열|인 경우는 대각선에 위치하는 경우이다.
이를 Math.abs() 메서드를 이용해 표기하는 것.
ex) 현재 행: 1,1 / 이전 행: 0,0이라 할 때, |1-0| == |1-0|이 성립되며 실제로 대각선에 위치한다.
셋째, 백트래킹 알고리즘을 위해 조건을 판단하는 isPossible() 메서드 구현하는 것을 간과한 것.
이전 퀸들의 범위에 걸치는 경우는 탐색에서 배제하는 메서드를 반드시 만들어야 한다.
위와 같은 실수를 하고 있는 분들은 참고하시면 좋을 것 같습니다.