문제 url:
N-Queen
문제:
🤔 문제 알아보기
백트래킹 예제에서 대표적인 문제라고 한다.
먼저, 체스판에서 Queen이 어떻게 움직이는지 살펴보자,
체스를 해본 경험이 있으신 분들은 아시겠지만, 퀸은 그냥 사기다. 모든행, 열 방향으로 전체 움직일 수 있는 사기캐릭이다.
이를 간단히 말하자면, 모든 행과 열 그리고 대각선 방향에는 퀸을 놔둘 수 없다.
그럼 문제 조건을 그림과 함께 살펴보면 현재 퀸이 만약 4,d 에 위치한다면,
화살표에 속하지 않은 곳에 퀸을 둘 수 있는 것이다. 이렇게 총 N개만큼 두는데,
문제 출력은 총 N개의 퀸을 두는 모든 경우의 수를 구하라고 하였다.
그럼 대충 코드화 시킨다면 대충 다음과 같이 구현할 수 있을 것이다.
if(queen == N) {
cnt++;
return;
}자!, 필자는 해당 문제를 2차원 배열 문제라고 판단하였고 이를 구현해보고자 했는데, 일단 구현에 실패하였다. 그래서 타 블로그 내용을 바탕으로 이해한 내용을 정리하고자 한다.
먼저, 퀸을 놔두는 경우의 수를 한번 그림으로 나타내보겠다.
N이 4인 경우의 4X4 크기의 체스판을 그려보면 다음과 같다.
현재 [2][0] 좌표에 퀸을 놔두었다고 가정하면, 다음 퀸을 둘 수 있는 공간은 위와 같을 것이다.
그럼 다음 1열에서 놔둘 수 있는 행은 총 1개 즉, [0][1]이 존재한다.
그럼 다음 2열에서 놔둘 수 있는 행은 총 1개 즉, [3][2] 만 가능하다.
[3][2] 위치에 퀸을 두면 자연스레 3열에는 1행만 남아 자동으로[1][3] 에 퀸이 위치하게 된다.
이렇게 총 N X N 크기의 체스판에 N개의 퀸을 놔두면 되는 문제이다.
아까 위에서 얘기했듯, 필자는 2차원 배열로 문제풀이를 생각했다. 하지만,
타 블로그들은 2차원 배열이 아닌 1차원 배열로 풀이를 진행했는데, 이를 이해한 바를 설명하자면,
그림을 봤을 때, 우리는 현재 열을 기준으로 퀸을 하나씩 놔둔 것을 기억할 것이다.
0열 -> 2행 / 1열 -> 0행 / 2열 -> 3행 / 3열 -> 1행
이를 배열로 나타내면 [2, 0, 3, 1] 으로 나타낼 수 있는 것이다.
즉! 열은 곧 해당 배열의 인덱스를 의미하고 인덱스 안의 값이 곧 행을 의미할 수 있다.
그러면 문제 조건이 조금더 간편해질 수 있다.
인덱스 번호를 통해 열을 나타낸다면, 우리는 각 열 마다 겹치는 행이 있는지만 확인하면 될 것이다.
즉, 첫 번째 그림을 봤을 때
[2][0]이 처음 들어갔을 때,
1열에는 2행을 제외한[0,1,3]행의 값들이 올 수 있다는 것.
이게 첫 번째 조건이다.하지만, 그림을 다시 보면
[0,1,3]행이 아닌[0]행만 가능하다.
그 이유는[1][1]과 [3][1]은[2][0]위치에서 대각선에 위치하기 때문이다.
이게 두 번째 조건이다.그럼 우리는 문제 조건을 총 2개로 볼 수 있는 것
- 앞에 위치하는 퀸들과 행이 같아서는 안된다.
- 앞에 위치하는 퀸들의 대각선 방향에 존재해서는 안된다.
이 두 조건을 가지고 문제를 풀어보자,
🐱👤 실제 코드
import java.io.*;
public class Main {
static int N;
static int[] chess_board;
static int res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
chess_board = new int[N];
dfs(0);
System.out.println(res);
}
static void dfs(int depth) {
if(depth == N) {
res++;
return;
}
/*
* 행을 이동하는 반복문
*/
for(int i = 0; i < N; i++) {
chess_board[depth] = i;
if(possibility(depth)) {
dfs(depth + 1);
}
}
}
static boolean possibility(int col){
for(int i = 0; i < col; i++) {
/*
* 현재 열 기준 행의 위치와 이전 퀸들의 행들의 위치를 비교
* 만약 같다면 false를 반환하여 다음 깊이로 이동하지 못하게 함
* 만약 같지 않다면, 해당 depth에는 해당 값을 저장
*/
if(chess_board[i] == chess_board[col]) {
return false;
}
if(col - i == Math.abs(chess_board[col] - chess_board[i])) {
return false;
}
}
return true;
}
}
😎 코드 풀이 및 해석
1번 코드
static void dfs(int depth) {
if(depth == N) {
res++;
return;
}
/*
* 행을 이동하는 반복문
*/
for(int i = 0; i < N; i++) {
chess_board[depth] = i;
if(possibility(depth)) {
dfs(depth + 1);
}
}
}dfs 메서드이다. 파라미터로 depth(깊이)를 받는데, 쉽게 말해서 chess_board배열의 인덱스라고 생각하면 된다.
왜? 배열의 인덱스를 열로 보는가??
우리는 위에서 조건을 읽어봤을 것이다. 모든 열에는 하나의 값만 존재할 수 있다. 이는 곧 퀸이 위치한 모든 열을 일일이 막을 필요가 없어지는 것이다.
그래서 코드가 단순해질 수 있는 것
자 그럼 열(depth)에 i(행)을 넣고, 해당 위치에 퀸을 놔둬도 되는지 검사하는 possibility 메서드를 호출한다.
만약 가능하다면 재귀호출을 통해 다음 열(depth)로 이동하여 새로운 해를 찾을 때까지 반복하게 될 것이고
그렇지 않으면 현재 열(depth)에서 해를 찾을 때 까지 i(행)를 반복해서 구할 것이다.
2번 째 코드
static boolean possibility(int col){
for(int i = 0; i < col; i++) {
/*
* 현재값과 비교했을 떄, col 인덱스 값이 null 혹은 0인 경우
* 같지 않아 false를 준다.
* 즉, 행이 같지 않다면 true, 그렇지 않으면 false 반환
*/
if(chess_board[i] == chess_board[col]) {
return false;
}
if(col - i == Math.abs(chess_board[col] - chess_board[i])) {
return false;
}
}
return true;
}possibility의 매개변수로 받는 값은 depth임을 기억하고 코드를 살펴보자
if(chess_board[i] == chess_board[col]) {
return false;
}현재 열에 속한 행의 값이 이전 열에 존재하는 행의 값과 일치 여부를 검토한다.
만약 일치하면 false를 반환해 열(depth)에 다른 값을 찾을 수 있도록 한다.
if(col - i == Math.abs(chess_board[col] - chess_board[i])) {
return false;
}해당 로직은 대각선에 위치한 값들을 제외시키기 위한 로직이다.
해당 코드는 그림과 함께 보면 이해가 빠르다.
현재 두 원은 대각선 선상에 놓여져있다. 이를 좌표로 나타내면
[2][1] 과 [0][3]으로 나타낼 수 있다.
그럼 해당 코드를 통해 계산해보자,
현재 col(depth)를 3으로 가정하고, i(열)을 1로 가정하자,
그럼 col - i = 3 - 1 = 2이다.
그 후 chess_board[col] - chess_board[i] = 0 - 2 = -2
Math.abs()는 절댓값을 구하는 메서드로 -2는 곧 2가 된다.
그러면 보자, col - i 를 한 값과 chess_board[col] - chess_board[i]를 한 값과 일치하다. 그 말은 즉슨 대각선에 위치하고 있다는 얘기이다.
이렇게 대각선의 위치 여부까지 알아볼 수 있다.
💜 참고자료
