[백준] 9663번 N-Queen (Java)

subbni·2024년 5월 3일

DFS 백준 백트래킹 코딩테스트

백준

목록 보기

14/24

9663번 문제

문제

문제를 보고 당황했다.
저기 .. 체스를 모르는 사람은 못 푸는 문제인가요? 🥲

체스룰부터 끄적끄적 검색해보았다 ...

문제를 풀기 위해 알아야 하는 룰은 아래와 같다.
(다행히 단 하나다. ~~이왕이면 문제에 좀 적어주지~~)

퀸은 상하좌우, 대각선으로 칸수에 관계없이 움직일 수 있다.

즉, N x N인 체스판 위에서 N개의 말(퀸)을 칸수에 관계없이 상하좌우, 대각선에 배치하지 않도록 하는 경우의 수를 구하는 문제이다.

풀이

처음 생각한 방법

int[][] visit 를 둔다.
visit[i][j]가 0인 경우, 퀸을 놓을 수 있는 자리로 생각한다.
visit[i][j]가 0인 경우, 해당 자리에 퀸을 하나 두고 dfs를 이어나간다.
→ 어떤 한 자리에 퀸을 뒀을 경우, 그 자리 포함 상하좌우와 대각선의 위치에 해당하는 visit[i][j]에 1을 더한다.
→ dfs를 빠져나오면 다시 1을 빼어 visit을 원상태로 복귀한다.

처음 문제를 봤을 때에는 2차원 배열을 두고, 백트래킹을 하는 방법을 생각했다.
그런데 이렇게 문제 풀이를 하다보니 상하좌우와 대각선을 처리하는 과정이 매우 복잡해지는 것을 경험 .. 하고 뭔가 이 방법은 비효율적인 것 같다는 생각을 하게 됨.

이렇게 풀다가는 시간만 낭비할 것 같아 풀이법을 확인해봤다. 애초에 N-Queen 문제는 유명하고 잘 알려진 문제 중 하나여서 풀이법을 공부하는 게 나을 것 같다는 판단.

역시나 1차원 배열로 쉽게 풀이하는 방법이 있었다.
이 블로그를 보고 1차원 배열로 어떻게 풀이를 해나갈지 완벽하게 이해할 수 있었다.

구현 코드

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

public class Main {
    static int N;
    static int[] ans;
    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());
        ans = new int[N];
        dfs(0);
        System.out.println(cnt);
    }

    public static void dfs(int depth) {
        if(depth == N) {
            cnt++;
            return;
        }

        for(int i=0; i<N; i++) {
            ans[depth] = i;
            if(checkPosition(depth)) {
                dfs(depth+1);
            }
        }
    }

    public static boolean checkPosition(int depth) {
        for(int i=0; i<depth; i++) {
            // 같은 행이 위치
            if(ans[depth] == ans[i]) {
                return false;
            }
            // 대각선 상 위치
            if(Math.abs(i-depth) == Math.abs(ans[i]-ans[depth])) {
                return false;
            }
        }
        return true;
    }

}