[알고리즘] 백준 9663 N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_9663 {
    static int n;
    static int[] map;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        n = Integer.parseInt(s);
        map = new int[n + 1];
        dfs(1);
        System.out.println(count);
    }

    static void dfs(int depth) {
        if (depth == n + 1) {
            count++;
            return;
        }

        for (int i = 1; i < n + 1; i++) {
            map[depth] = i;

            if (checkMap(depth)) {
                dfs(depth + 1);
            }
        }

    }

    static boolean checkMap(int row) {

        for (int i = 1; i < row; i++) {
            if(map[row] == map[i])
                return false;

            if (Math.abs(i - row) == Math.abs(map[row] - map[i]))
                return false;
        }
        return true;
    }


}

 

아주 유명한 백트래킹 예제이다.

 

처음에는 2차원배열을 통해서 문제를 해결하려고 했는데 풀리지가 않아서 다른 분들의 소스코드를 참고해서 풀었다.

 

1차원 배열을 통해서 체스판을 나타내고 문제를 해결했다.

 

map[x] = y가 있을 때,  x는 행의 좌표를 나타내며 y는 열의 좌표를 나타낸다.

 

문제 조건에서, 각 행마다 퀸은 무조건 하나씩 존재하기에

 

for (int i = 1; i < n + 1; i++) {
            map[depth] = i;

            if (checkMap(depth)) {
                dfs(depth + 1);
            }
        }

위와 같이 재귀호출을 할 수 있다. 현재 depth에서 퀸을 놓을 수 있는 자리면 다음 depth로 dfs를 수행한다.

 

static boolean checkMap(int row) {

        for (int i = 1; i < row; i++) {
            if(map[row] == map[i])
                return false;

            if (Math.abs(i - row) == Math.abs(map[row] - map[i]))
                return false;
        }
        return true;
    }

 

위는 현재 위치에 퀸을 둘 수 있는지 판별하는 메소드이다. 

 

1) 퀸이 동일한 칼럼에 있는 경우

    map[x] = y 에서 좌표는 x,y 이기 때문에 map[row]와 map[i]를 비교하면 동일한 칼럼에 위치하는지 알 수 있다.

 

2) 퀸이 대각선에 존재하는 경우

    두 좌표의 row값을 서로 뺀것과 column값을 서로 뺀것의 절대값이 같으면 대각선에 위치한 것이다.

 

위 조건 두개를 비교하여 재귀를 돌림으로써 문제를 해결하였다.