문제 출처

단계별로 풀어보기 > 백트래킹 > N-Queen
https://www.acmicpc.net/problem/9663

문제 설명

접근 방법

행에 따른 열의 값을 저장하는 chess 배열을 생성한다. chess 배열은 i번째 행에 j번째 열에 퀸이 있음을 뜻한다.(chess[i] = j;)

chess의 행에 따른 어떤 값의 열을 넣을지 dfs를 통해 0~chess의 크기까지 반복을 진행한다.
이 과정에서 possible 메서드를 통해 같은 열에 있는 경우, 대각선에 있는 경우를 확인하여, 놓으려고 하는 퀸의 경로에 이미 퀸이 놓아있으면 false를 return하여 해당 자리는 두지 못하게 한다.

import java.io.*;

public class N_Queen {
    static int[] chess;
    static int count;
    static int size;

    public static void dfs(int depth) {
        if (depth == size) {  // 모든 행에 퀸을 배치 완료하면 count 증가
            count++;
            return;
        }

        for (int i = 0; i < size; i++) {  // 가능한 모든 열 탐색
            chess[depth] = i;  // 현재 depth 행의 i 열에 퀸 배치
            if (possible(depth)) {
                dfs(depth + 1);  // 다음 행 탐색
            }
        }
    }

    public static boolean possible(int depth) {
        for (int i = 0; i < depth; i++) {  // 이전 행들과 비교
            if (chess[i] == chess[depth]) return false;  // 같은 열에 있는 경우
            if (Math.abs(i - depth) == Math.abs(chess[i] - chess[depth])) return false;  // 대각선에 있는 경우
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        size = N;
        chess = new int[N];
        count = 0;

        dfs(0);

        bw.write(String.valueOf(count));
        br.close();
        bw.flush();
        bw.close();
    }
}

Review

import java.io.*;

public class BOJ_9663_N_Queen_review {
    static int count; // 퀸을 놓을 수 있는 총 갯수
    static int[] chess; // x번째 행, y번째 열에 퀸이 있음을 표시

    // dfs 접근
    public static void dfs(int depth){
        if(depth == chess.length){ // 모든 행에 퀸을 두면 dfs return
            count++;
            return;
        }
        // 반복문 통해서 depth 행에 여러 열을 둬서 경우의 수 확인
        for(int i = 0; i<chess.length; i++){
            chess[depth] = i;
            if(possible(depth)){ // 해당 depth 행에 i열에 놓은 것이 가능하면 depth+1 로 넘어감
                dfs(depth+1);
            }
        }
    }

    public static boolean possible(int depth){

        for(int i = 0; i<depth; i++){
            if(chess[depth] == chess[i] || Math.abs(depth - i) == Math.abs(chess[depth] - chess[i])) return false;// 이전까지의 행에 같은 열에 퀸이 있는지 확인, 대각선 위치에 퀸이 있는지 확인
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        count = 0;
        chess = new int[N];

        dfs(0);

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();


    }
}

알게된 점

대각선에 퀸 여부를 확인할 때, |행 - 행| == |열 - 열|이 조건임을 예시를 들어가며 직접 이해해봤다.
ex) (3,4)에 퀸을 두는 경우, (1,2)에 퀸이 있으면 |3-1| == |4-2| 로 2 == 2가 성립한다.

처음 이 문제를 풀 때, 일반적인 dfs문제의 접근 방식인 visited 배열을 만들어서 풀어보려했다. 하지만 단순하게 생각하여, visited 배열을 2차원 배열로 설정했고, 그럼 이에 따른 한 곳에 퀸을 두었을 때, visited[행][모든 열], visited[모든 행][열], visited[행+-i][열+-i]를 모두 true로 변경하고 다시 false로 변경해야하는 엄청난 과정을 진행해야함을 보고 잘 못생각했다고 판단했다.

출처
https://st-lab.tistory.com/118

문제푼 흔적

Review