[Java] 프로그래머스 - N-Queen

n x n 체스판에서 서로 공격할 수 없도록 퀸 n개를 배치하는 경우의 수를 구하는 문제

 

1. 문제 유형

백트래킹, DFS, 재귀

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 처음에는 int[][] map으로 체스판 전체를 만들고, 퀸을 놓을 수 있는지 매번 검사하려고 했다.

이 방식 자체가 틀린 것은 아니지만, 문제를 너무 체스판 전체 탐색으로 바라봐서 복잡하게 느껴졌다.
특히 현재 위치에 퀸을 놓을 수 있는지 검사할 때 위쪽 행의 모든 칸을 다시 확인해야 해서 흐름이 잘 안 잡혔다.

오답 원인: 처음에는 dfs()가 체스판 전체를 탐색하는 함수처럼 느껴졌는데, 한 번의 DFS 호출은 현재 행에 퀸을 어디에 둘지 선택하는 단계였다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 퀸은 같은 열, 같은 대각선에 있으면 서로 공격할 수 있다.
한 행에 퀸을 하나씩 놓는 방식으로 풀 수 있기 때문에, 같은 행은 따로 검사하지 않아도 된다.

풀이 아이디어:

1. row번째 행에서 가능한 모든 col을 시도한다.
2. 현재 위치 (row, col)에 퀸을 놓을 수 있는지 확인한다.
3. 가능하면 queens[row] = col로 저장하고 다음 행으로 이동한다.
4. row == n이 되면 퀸 n개를 모두 배치한 것이므로 정답 개수를 증가시킨다.

4. 구현 코드

class Solution {
    int[] queens;
    int count = 0;
    int size;

    public int solution(int n) {
        size = n;
        queens = new int[n];

        dfs(0);

        return count;
    }

    public void dfs(int row) {
        if (row == size) {
            count++;
            return;
        }

        for (int col = 0; col < size; col++) {
            if (canPlace(row, col)) {
                queens[row] = col;
                dfs(row + 1);
            }
        }
    }

    public boolean canPlace(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col) {
                return false;
            }

            if (Math.abs(row - i) == Math.abs(col - queens[i])) {
                return false;
            }
        }

        return true;
    }
}

시간 복잡도: O(N)? / 공간 복잡도: O(N)

---

 

인사이트

• 문제를 풀 때 자료구조를 어떻게 잡느냐에 따라 구현 난이도가 크게 달라진다는 걸 느꼈다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/12952