[백준, Java] 9663번 : N-Queen

🔗 문제 링크

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

😮 문제 해결 방법

첫 번째 행부터 차례로 모든 배치에 퀸을 놓아보는 방식의 완전탐색 문제이다.

퀸을 배치하기 전에 이전 행에 놓인 퀸 들이 움직일 수 없는 위치에 놓아야 하기 때문에 행 마다 퀸을 배치하면서 이전 행의 퀸의 배치와 겹치지 않는지 판단하는 로직을 추가한다.

 

이전 행의 퀸들과 겹칠 수 있는 경우는 2가지가 있다.

1. 이전 행들에 놓인 퀸의 열과 현재 놓을 퀸의 열이 동일한 경우
2. 이전 행들에 놓인 퀸과 현재 놓을 퀸이 대각선에 존재하는 경우

동일한 행에 퀸이 놓이는 경우도 고려해야하지만, 재귀를 이용해 한 행 (depth)마다 퀸을 배치할 것이기 때문에 동일한 행에 두 개이상의 퀸이 놓이는 경우는 발생하지 않는다.

 

각 행 (depth)마다 퀸의 열 위치를 저장할 pos 배열을 이용한다.

예를 들어, pos[2]는 2인데 이는 2행 2열에 퀸이 놓아져 있다는 뜻이다.

 

pos 배열을 이용해 이전 퀸의 행과 열을 판단할 수 있고, 매 행마다 현재 퀸을 배치할 행과 열을 알 수 있기 때문에 이를 기반으로 퀸을 놓을 수 있는지를 판단한다.

1번 조건을 판단할 때는 pos[이전 행]과 현재 퀸을 배치할 열을 이용해 판단한다.

 

2번 조건을 판단할 때는 이전 행과 현재 행의 차이, 이전 행들에 놓인 열과 현재 열 차이의 값이 동일한 경우 는 대각선에 놓인 경우임을 알 수있다.

따라서, |pos[이전행] - 현재 열| == |이전 행 - 현재 열| 인 경우 대각선에 위치하는 경우이다.

curRow - row == curCol - pos[row]는 대각선에 배치되는 경우

🚩 Java 코드

package com.algorithm.Baekjoon;

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

public class Main_9663_NQueen {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] pos = new int[N];

        int rst = nQueen(N, pos);
        System.out.println(rst);
        br.close();
    }

    private static int count;
    private static int nQueen(int N, int[] pos) {
        count = 0;

        putQueen(0, pos, N);

        return count;
    }

    private static void putQueen(int row, int[] pos, int n) {
        // 모든 행에 퀸을 다 배치한 경우 개수 증가
        if(row == n) {
            count++;
            return;
        }

        // 0번째 열 부터 n 번재 열 까지
        for(int col = 0; col < n; col++) {
            pos[row] = col; // 현재 행의 퀸의 열위치를 저장

            if(possible(row, col, pos)) {
                putQueen(row + 1, pos, n);
            }
        }
    }

    // 현재 위치에 퀸을 배치할 수 있는지 판단
    private static boolean possible(int curRow, int curCol, int[] pos) {
        // 첫 번째 행부터 현재 행 까지 놓인 퀸을 판단
        for(int row = 0; row < curRow; row++) {
            // 1. 이전에 놓인 퀸의 열과 현재 퀸의 열이 동일하면 겹치는 경우이므로 false
            if(pos[row] == curCol) return false;

            // 2. "이전 행과 현재 행의 차이"와 "이전 행의 열과 현재 행의 열의 차이"가 동일한 경우는 대각선에 퀸이 놓인 경우이므로 겹치는 경우 false
            if(Math.abs(row - curRow) == Math.abs(pos[row] - curCol)) return false;
        }
        // 3. 이외의 경우는 겹치지 않는 경우
        return true;
    }
}