[문제 풀이] 백준 9663번 N-Queen JAVA

문제

 

  문제접근 방법   

해당 문제는 N x N크기의 체스판이 존재하고 N개의 퀸이 충돌하지 않는 경우의 수를 구하는 프로그램을 작성하는 문제로

N은 입력값으로 주어진다. 

처음 문제를 읽고 DFS를 통해 문제 해결이 가능할 것 같다는 생각은 했지만 대각선처리에 대한 생각이 많아져 어려움이 있었다.

그래서 대각선을 고려하지 않고 초반에는 행과 열만 어떤 식으로 제한할지를 먼저 고민했다.

그럼 체스에서 퀸이 어떤식으로 움직이는지를 알아야 하는데 퀸은 본인 위치 기준 상하좌우 우상 좌상 좌하 우하 대각선의 칸의 끝까지 움직일 수가 있다.  이미지로 보면 아래와 같이 움직일 수가 있는 것이다.

이처럼 상하좌우 대각선 모든 범위를 제외하고 충돌하지 않는 N개의 퀸의 경우의 수를 구하는 것이다.

그렇다면 어떤 경우가 가능한지 직접 작성해 보기로 결정하였다. N이 5일 때 기준으로 그림을 그려보았다.

이런 식으로 그리고 0,0을 시작으로 퀸을 하나씩 그려보니 여러 결과가 존재하지만 아래와 같이 한 행 한열에는 하나의 값만이 존재해야 한다는 것을 확인하였다. 아래는 본인이 그려본 진행 순서이다.

 

1. (0,0)칸에 퀸을 놓는 경우

0,0 칸에 퀸을 놓게 되면 해당 이미지의 파란색 부분에는 더 이상 퀸을 놓을 수가 없다. 

 

2. (1,2)칸에 퀸을 놓는 경우

위에서 남은 칸들중 여러 칸이 있지만 여러 경우 중 하나만을 보여주는 것이므로 1,2에 퀸을 배치하였다.

 

3. (2,4)칸에 퀸을 놓는 경우

 

4. (3,1)칸에 퀸을 놓는 경우

 

5. (4,3)칸에 퀸을 놓는 경우

이런 식으로 퀸을 N개 배치하려면 하나의 행 그리고 하나의 열에는 하나씩만 들어갈 수 있음을 확인할 수 있다.

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static boolean visitedPlus[];
    public static boolean visitedMinus[];
    public static int chessBoard[][];
    public static int cnt=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        chessBoard=new int[n][n];
        visited=new boolean[n];

        // n개의 퀸이 충돌하지 않는 경우는 각행마다 한개씩 존재
        dfs(0);
        System.out.print(cnt);
    }
    public static void dfs(int depth){
        if(depth==visited.length){
            cnt++;
            return;
        }
        for(int i=0;i<visited.length;i++){
            if(!visited[i]){
                visited[i]=true;
                dfs(depth+1);
                visited[i]=false;
            }
        }
    }
   
}

위에서도 설명하였듯 대각선을 신경 쓰지 않고 상하좌우만 신경 써서 작성한 코드이다. 우선 dfs를 호출해 주고 깊이가 n일 때까지 반복 후 깊이가 n이 되면 함수를 종료하면서 충돌하지 않는 경우의 수 cnt를 증가시키는 흐름이다. 

dfs에서 처음에는 방문처리를 해주는 visited를 이중배열로 선언하고 관리하려 했지만 가능은 해 보이지만 너무 많은 호출로 시간복잡도가 늘어나 비효율적이고 열과 대각선을 완전히 따로 관리해야 해서 중복 계산의 위험이 있다는 것을 확인하였다.

그래서 depth 깊이를 행 for문의 i를 열로 두고 visited를 1차원 배열로 선언하고 열의 방문만을 처리하는 것으로 설정하였다. 

이유는 depth는 어차피 0~n-1까지 순서대로 반복되어 중복이라는 것이 없기 때문에 행의 방문처리는 끝난 것으로 보기 때문에 열만 visited에서 별도로 방문처리를 해주는 것이다. 이렇게 되면 대각선만을 고려하면 문제를 해결할 수 있는데 아래와 같이 숫자를 좌표로 적어두고 문제를 보다가 방법이 떠올라 코드를 작성하였다.

위의 이미지처럼 체스판에 각각의 칸이 가지는 행열 좌표를 작성하고 대각선을 유심히 본결과 ↘↖ 방향의 한 대각선 상에 놓여있는 행과 열의 차가 같고  ↗↙ 방향 한 대각선상에 놓여있는 칸들은 행과 열의 합이 같다는 특징을 발견하였다.

예를 들어 (0,0)(1,1)....(3,3), (4,4) 대각선을 보면 ↘↖ 방향의 대각선이고 행과 열을 빼면 모든 값이 0인 것을 확인해 볼 수 있다.

이를 활용해 배열에 방문처리를 해주면 2차원 배열을 사용하여 일일이 방문처리할 필요도 없고 훨씬 효율적인 코드를 작성할 수 있는 것이다. 이를 코드로 구현하면 다음과 같다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static boolean visitedPlus[];
    public static boolean visitedMinus[];
    public static int chessBoard[][];
    public static int cnt=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        chessBoard=new int[n][n];
        visited=new boolean[n];
        visitedPlus=new boolean[2*n-1];
        visitedMinus=new boolean[2*n-1];
        
        // n개의 퀸이 충돌하지 않는 경우는 각행마다 한개씩 존재
        dfs(0);
        System.out.print(cnt);
    }
    public static void dfs(int depth){
        if(depth==visited.length){
            cnt++;
            return;
        }
        for(int i=0;i<visited.length;i++){
            if(!visited[i]&&!visitedPlus[depth+i]&&!visitedMinus[depth-i+(visited.length-1)]){
                visited[i]=true;
                visitedPlus[depth+i]=true;
                visitedMinus[depth-i+(visited.length-1)]=true;
                dfs(depth+1);
                visited[i]=false;
                visitedPlus[depth+i]=false;
                visitedMinus[depth-i+(visited.length-1)]=false;
            }
        }
    }
   
}

위에서 언급하였던  ↗↙ ,  ↘↖ 방향의 대각선들은 각각 처리가 다르므로 별도로 배열을 두 개 선언해 주고 하나는 인덱스를 

행-열+(n-1)로 하나는 행+열로 해당하는 인덱스의 방문처리를 해주면 퀸이 이동할 수 있는 경로의 대각선을 모두 방문처리한 게 되는 것이다. 여기서 행-열 +(n-1)은 도대체 왜인가를 생각할 수 있는데 n이 5 기준으로  ↗↙ ,  ↘↖방향중 한 방향의 대각선을 개수를 세어보면 2 x n -1 개의 대각선을 확인할 수 있는데 행 -열을 할 경우 음수 값이 발생하게 된다. 배열에서는 인덱스가 음수값일 수가 없으므로 음수가 양수가 될 수 있도록 n-1을 더해서 처리해 주는 것이다.

 

  마무리  

해당 코드는 DFS알고리즘에서 대각선을 어떤 식으로 접근해서 문제를 해결하는지를 보여주는 좋은 문제였다. 많은 시간이 소요되었고 많은 생각과 고민을 하였는데 규칙이 보여서 풀 수 있었지만 실제 코딩테스트라던지 어떤 시간이 제한된 상황에서 처음 접한다면 풀기는 쉽지 않을 것이라고 생각된다.