자바(Java) 백준 9663 N-Queen 풀이

문제

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

9663번: N-Queen

풀이

유명한 N-Queen 문제를 풀면 된다. 예전에 대학교 알고리즘 수업 때 c++로 백트래킹을 써서 풀어 본적이 있었는데 이번에 자바로 다시 한번 풀어보았다. 제가 푼 방식은 다음과 같습니다.

• 1) 세로로 인덱스 0부터 n - 1까지 퀸을 하나씩 배치할 것입니다.
• 2) dfs를 사용하여 세로 -> 가로 순으로 0 ~ n - 1까지 해당 지점에 퀸을 놓을 수 있는지 확인합니다.
• 3) isPos() 메서드를 통해 3가지 경우의 수를 확인합니다.
  • 해당 지점 부터 위에 퀸이 존재하는지
  • 해당 지점으로부터 왼쪽 위 대각선에 퀸이 존재하는지
  • 해당 지점으로부터 오른쪽 위 대각선에 퀸이 존재하는지
• 4) n개의 퀸을 모두 배치했다면 카운트 해주면 됩니다.

코드

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

public class Main {

    private static int n;
    private static int[][] board;
    private static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        board = new int[n][n];

        dfs(0);

        System.out.println(cnt);
    }

    public static void dfs(int idx) {
        if (idx == n) {
            cnt++;
            return;
        }

        // 해당 지점에 퀸을 놓을 수 있다면 놓은 지점을 1로 체크하고 dfs 순회합니다.
        for (int i = 0; i < n; i++) {
            if (isPos(idx, i)) {
                board[idx][i] = 1;
                dfs(idx + 1);
                board[idx][i] = 0;
            }
        }
    }

    // 해당 지점에 퀸을 놓을 수 있는지 확인합니다.
    public static boolean isPos(int x, int y) {
        // 해당 지점의 세로 위로 퀸이 위치하는지 확인합니다.
        for (int i = 0; i < x; i++) {
            if (board[i][y] == 1) {
                return false;
            }
        }

        for (int i = 1; i <= x; i++) {
            if (x - i >= 0 && y - i >= 0 && board[x - i][y - i] == 1) {
                // 해당 지점의 왼쪽 위 대각선으로 퀸이 위치하는지 확인합니다.
                return false;
            } else if (x - i >= 0 && y + i < n && board[x - i][y + i] == 1) {
                // 해당 지점의 오른쪽 위 대각선으로 퀸이 위치하는지 확인 합니다.
                return false;
            }
        }

        return true;
    }
}