백준 9663번 N-Queen :: 마이구미

이번 글은 백준 알고리즘 문제 9663번 "N-Queen" 을 다뤄본다.

백트래킹하면 바로 이 문제라고 알려져있을 정도로 유명하다고 한다.

그렇다. 백트래킹을 통해 문제를 풀이해보자.

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

체스의 룰을 알아야겠지만, 크게 문제가 되지 않는다.

퀸은 배치된 칸을 기준으로 오와 열, 그리고 대각선 이동이 가능한 가장 가치있는 기물이다.

퀸을 배치할 수 있는 경우를 보면 확실히 이해를 할 것이다.

            

문제는 N x N 체스판 위에 N개를 놓는 경우를 구한다.

N개를 놓는 경우와 퀸을 성질을 통해 얻을 수 있는 것이 있다.

=> 각 행 또는 열에는 퀸이 오직 하나만 올 수 있다.

이것을 파악한다면, 조금 더 빠르게 문제 접근을 이해할 수 있다.

본인은 정점을 행을 기준으로 두었다.

private void solve() {
    n = sc.nextInt();

    for (int i = 1; i <= n; i++) {
        col = new int[15];
        col[1] = i;
        // 정점은 행을 기준. (i = 1) => 1행(1열), (i = 2) => 2행(1열), (i = 3) => 3행(1열) 
        dfs(1);
    }
    System.out.println(ans);
}

col 배열은 인덱스를 열이라고 하고, 값을 행이라고 한다.

1행 1열, 2행 1열, 3행 1열 .... 순으로 DFS를 돌리는 흐름이다.

이 말은 아래 그림을 보면, 이해하기 쉽다.

다시 말하자면, 그림에서 루트에서 나오는 4개의 경우를 볼 수 있다.

1행 1열, 2행 1열, 3행 1열, 4행 1열이라는 것을 볼 수 있다.

첫번째 for문은 1행 1열을 기준으로 DFS를 시작해서 깊게 탐색하고, 2번째 for문은 2행 1열을 기준으로 다시 DFS를 시작하는 흐름이다.

3번째, 4번째도 마찬가지다.

DFS는 백트래킹을 고려하여 구현한다.

public static void dfs(int row) {
    if (row == n) {
        ++ans;
    } else {
        for (int i = 1; i <= n; i++) {
            col[row + 1] = i;
            if (isPossible(row + 1)) {
                dfs(row + 1);
            } else {
                col[row + 1] = 0;	
            }
        }
    }
    // 백트래킹되는 시점이기에 방문 기록을 없애준다.
    col[row] = 0;
}

isPossible함수는 퀸이 배치될 수 있느냐를 판단하는 곳이다.

public static boolean isPossible(int c) {
    // col[1]의 의미는 1행 *열이다.
    // col[1] = 1 => 1행 1열, col[2] = 3 => 2행 3열

    // 이전 열들을 탐색하면서 배치 가능 여부 확인
    for (int i = 1; i < c; i++) {
        // 같은 행, 열
        if (col[i] == col[c]) {
            return false;
        }
        // 대각선
        if (Math.abs(col[i] - col[c]) == Math.abs(i - c)) {
            return false;
        }
    }
    return true;
}

col은 퀸이 배치한 행과 열을 알고 있다.

이전 퀸들을 확인하면서 가능 여부를 판단하면 된다.

백트래킹 참고 링크

http://ddmix.blogspot.kr/2015/06/cppalgo-29-greedy-backtracking.html

static int ans, n;
static int[] col;
 
private void solve() {
    n = sc.nextInt();
 
    for (int i = 1; i <= n; i++) {
        col = new int[15];
        col[1] = i;
        // 정점은 행을 기준. (i = 1) => 1행(1열), (i = 2) => 2행(1열), (i = 3) => 3행(1열) 
        dfs(1);
    }
    System.out.println(ans);
}
 
public static void dfs(int row) {
    if (row == n) {
        ++ans;
    } else {
        for (int i = 1; i <= n; i++) {
            col[row + 1] = i;
            if (isPossible(row + 1)) {
                dfs(row + 1);
            } else {
                col[row + 1] = 0;    
            }
        }
    }
    col[row] = 0;
}
 
public static boolean isPossible(int c) {
    // col[1]의 의미는 1행 *열이다.
    // col[1] = 1 => 1행 1열, col[2] = 3 => 2행 3열
 
    // 이전 열들을 탐색하면서 배치 가능 여부 확인
    for (int i = 1; i < c; i++) {
        // 같은 행, 열
        if (col[i] == col[c]) {
            return false;
        }
        // 대각선
        if (Math.abs(col[i] - col[c]) == Math.abs(i - c)) {
            return false;
        }
    }
    return true;
}