Skip to main content

[백트래킹] N-Queen

프로그래머스 N-Queen https://school.programmers.co.kr/learn/courses/30/lessons/12952

1. 문제

  • 가로, 세로 길이가 n인 정사각형으로 된 체스판인 있다.
  • 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하려고 한다.
  • 예를 들어서 n이 4인 경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격할 수 없다.

image.png

image.png

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족하도록 배치할 수 있는 방법의 수를 return하는 solution 함수 만들기

  • 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있다.
  • n은 12이하의 자연수이다.

2. 접근 방법

전형적인 백트래킹 문제이고 DFS로 상태공간 트리를 구현해서 푸는 문제이다. 백트래킹은 모든 경우의 수를 고려해서 해를 찾는 방식이다. 이름에서 유추할 수 있듯이 퇴각 검색(추적)이라는 뜻이다. 즉, 해를 찾기 위해서 후보군을 나열하고, 루트 노드부터 시작해서 제약 조건을 점진적으로 체크한다. 만약 조건에 맞지않다면, 뒤로 돌아와서(backtrack), 바로 다음 후보군으로 넘어간다. 백트래킹에서 검색할 후보들을 상태 공간 트리(State Space Tree)로 표현한다.

  • Promising : 해당 루트가 조건에 맞는지 검사하는 기법
  • Pruning(가지치기) : 조건에 맞지 않으면 포기하고, 다른 루트로 바로 돌아서서 탐색의 시간을 절약한다.

3. 정답코드

class Solution {
    int count; // 클래스 레벨 변수로 선언

    public int solution(int n) {
        count = 0;
        int[] queens = new int[n]; // index: 행, value: 열
        placeQueen(0, n, queens);
        return count;
    }

    // row: 현재 배치할 행, n: 체스판 크기, queens: 현재까지 배치된 퀸 정보
    private void placeQueen(int row, int n, int[] queens) {
        if (row == n) {
            count++; // 모든 행에 퀸 배치 완료
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isAvailable(row, col, queens)) {
                queens[row] = col; // 퀸 배치 
                placeQueen(row + 1, n, queens); // 다음 행 재귀 호출
            }
        }
    }

    // 현재 위치에 퀸을 놓을 수 있는지 체크
    private boolean isAvailable(int row, int col, int[] queens) {
        for (int i = 0; i < row; i++) {
            // 같은 열 또는 대각선에 퀸이 있는 경우
            if (queens[i] == col || Math.abs(queens[i] - col) == row - i) {
                return false;
            }
        }
        return true;
    }
}

배열로 풀었다. 이 문제는 이미체스판이 4*4로 고정되어 있기 때문에 동적 크기 관리 없이 배열을 쓴 것이다.

전체 흐름은 이렇게 짰다.

  • count 초기화: 가능한 배치 수를 세기 위한 변수
  • queens 배열 생성: 각 행에 어떤 열에 퀸이 놓였는지 저장
  • 첫 번째 행(row = 0)부터 재귀 호출 시작
  • 마지막에 총 경우의 수 반환

1. placeQueen(int row, int n, int[] queens)

  • 현재 행(row)에 퀸 놓는 함수이다
  • 종료 조건은 row == n 이렇게 되면 모든 행에 퀸 배치가 완료 된 상태니까 count++을 한다.
  • 반복문으로 0 ~ n-1열까지 퀸을 놓을 수 있ㄴ느지 검사한다.
  • isAvailable 체크 후 가능하면
    • queens[row] = col : 현재 행에 퀸 배치 기록
    • placeQueen(row + 1, ...) → 다음 행 탐색(재귀)

queens[row] = col

  • queens 배열은 각 행(row)에 어떤 열(col)에 퀸이 있는지 기록하는 용도이다.
  • 배열에서 queens[i] = j 라면 i행 j열에 퀸을 배치하는 것이다.
  • 예를 들어, queens[2] = 3이면 2행 3열에 퀸이 놓였다는 의미이다.
  • 이 한 줄이 바로 퀸을 체스판에 놓는 것처럼 기록하는 코드이다.
  • 실제로 체스판을 그리지 않고 배열로 위치 정보만 저장한다.

placeQueen(row + 1, n, queens)

  • row + 1 → 다음 행(row)에 퀸을 놓기 위해 재귀 호출
  • 즉, 현재 행에 퀸을 배치한 상태에서 다음 행 탐색을 시작하는 것이다.

2. isAvailable 메서드

  • 현재 위치 (row, col)에 퀸을 놓을 수 있는지 검사하는 함수이다.
  • 검사 대상: 현재 행보다 위에 있는 퀸들 (i < row)
  • 체크 조건:
    • queens[i] == col → 같은 열에 이미 퀸 있음 → 놓을 수 없음
    • Math.abs(queens[i] - col) == row - i → 대각선에 퀸 있음 → 놓을 수 없음
  • 둘 다 아니면 안전 → true 반환

대각선 탐색

Math.abs(queens[i] - col) == row - i

i행에 놓인 퀸의 열 위치에서 현재 놓으려는 퀸의 열 위치를 뺀 값과 현재 퀸을 놓으려는 행과 이미 퀸이 놓인 이전 행을 비교하는 것이다.
체스에서 퀸은 가로,세로, 대각선으로 공격 가능한데 두 좌표가 대각선에 있으면 행차이 = 열차이라는 특성을 이용한것이다.

다시말해

Math.abs(행1 - 행2) == Math.abs(열1 - 열2)

여기서:

  • 행1 - 행2 → row - i
  • 열1 - 열2 → col - queens[i]

그래서 대각선 충돌 체크는 아래와 같다.

Math.abs(queens[i] - col) == row - i

예를 들어, 퀸이 (2,3)에 있고, 새로운 퀸을 (4,5)에 두려고 하면

  • 행 차이: 4 - 2 = 2
  • 열 차이: 5 - 3 = 2

둘이 같으므로 대각선 공격 가능 → 놓을 수 없음 원리이다.

isAvailable 메서드 범위

for (int i = 0; i < row; i++)

i는 이전에 배치한 퀸들의 행 번호를 나타낸다. 현재 퀸을 놓으려는 row보다 작은 행들만 확인하면 충분하기 때문에 범위가 이렇게 된다. 왜냐하면 백트래킹은 위에서 아래로 한 행씩 퀸을 배치하기 때문에, row 이후 행에는 아직 퀸이 없기 때문이다. 즉 현재 퀸보다 윗 행에 있는 퀸들만 확인하는 것이다.

예: 현재 퀸을 3행에 놓으려면

  • 0, 1, 2행에 이미 놓인 퀸들과만 충돌 체크
  • 3행 이후는 아직 배치 안 됨 → 체크 불필요

처음에는 i <= row랑 i < queens.length로 해서 틀렸는데 row 이전 행까지만 검사해야 이미 놓은 퀸들과의 충돌 체크가 가능하다.


Back to top