[백준] Gold IV. N-Queen

https://www.acmicpc.net/problem/9663

 

사용 알고리즘

• 백트래킹

풀이

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

public class Main {
    static int n;
    static int [] arr;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        func(0);
        System.out.println(count);
    }

    public static void func(int depth) {
        if (depth == n) {
            count++;
            return;
        }

        for(int i = 0; i < n; i++){
            arr[depth] = i;
            if (possible(depth)) {
                func(depth + 1);
            }
        }
    }

    public static boolean possible(int depth) {
        for(int i = 0; i < depth; i++) {
            if (arr[i] == arr[depth]) return false; // 같은 열에 위치하는지 y좌표 확인

            else if (Math.abs(depth - i) == Math.abs(arr[depth] - arr[i])) return false; // 열의 차와 행의 차가 같은 경우 -> 대각선
        }
        return true;
    }
}

회고

 

문제 풀이를 보기 전에는 갈피를 잡기 힘든 문제였다. 문제 풀이를 보고 얻은 힌트 두개는

• N의 범위가 작다. (1 ~ 15) => 백트래킹을 고려할 수 있다.
• 2차원 배열로 푸는 대신에, 1차원 배열을 활용하는 편이 편하다

문제에선, row를 기준으로 처음에 퀸을 둘 곳을 찾는다. 그러고 나서, possible 메서드를 통해서 다음 col에 퀸을 둘 수 있는지 판별한다.

(0,0)에 퀸을 놓았을 때

 

위 그림은 맨 처음 지점에 퀸을 놓았을 때를 가정했는데 퀸의 숫자가 N-1밖에 안되므로 이 지점에는 놓을 수 없다.

 

row = 2일때 퀸을 배치

 

row가 2일때 퀸을 배치한다고 가정하면, 모든 depth(col)에 대해서 퀸을 배치할 수 있으므로, count를 1 늘려준다.

 

다음 depth에 대해서 퀸을 배치할 수 없는 조건은

• 같은 열에 존재하는지
• 대각선 내에 존재하는지
  • 열의 차와 행의 차가 같은 경우, ex) (1,1) , (3,3)에서 각 차이가 2 이므로 대각선에 존재한다.