[백준] 9663번: N-Queen

문제 링크

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

 

 

---

 

 

풀이 과정

체스판의 0번째 행부터 차례대로 퀸을 위치시키는 방식으로 해결했다.

 

아래 코드에서 loc이 퀸의 위치를 저장시키는 배열이며 인덱스가 행을, 대응하는 원소값이 열을 의미하는 것을 전제로 한다.

 

행을 매개변수로 받는 sol 메소드 내에서 현재 행에 대한 모든 열을 검사해 유효한 점에서 다음 행의 sol 메소드를 재귀 호출한다.

 

이때 행값을 매개변수로 받는 check 메소드가 sol 내에서 호출되어 현재 행 이전에 위치한 모든 퀸의 동선(열, 대각선 방향)과 겹치지 않는지 확인한다.

 

재귀를 통해 최종적으로 sol(n)이 호출되면 지금까지 퀸 n개의 배치가 유효하다는 뜻이므로 count를 1 증가시킨다.

 

sol 메소드가 이러한 로직을 따르므로 main 메소드에서 sol(0)을 호출하여 n개의 퀸을 배치할 수 있는 모든 경우를 검사할 수 있다.

 

 

---

 

 

코드

import java.util.*;
import java.io.*;

class Main {
    static int[] loc;
    static int n;
    static int count;

    static void sol(int row) {
        // 재귀 호출이 계속 이어져 끝까지 도달했으면 카운트
        if(row == n) {
            count++;
            return;
        }

        for(int col = 0; col < n; col++) {
            // 현재 행에 대한 열(즉 현재 위치) 설정
            loc[row] = col;
            
            // 유효한 위치라면 다음 행 재귀 호출
            if(check(row)) {
                sol(row + 1);
            }
        }
    }
    // 현재 위치가 유효한지 체크하는 메소드
    static boolean check(int row) {
        for(int prev = 0; prev < row; prev++) {
            // 같은 열에 있으면 false
            if(loc[prev] == loc[row]) {
                return false;
            }
            // 같은 대각선 위에 있으면 false
            if(Math.abs(row - prev) == Math.abs(loc[row] - loc[prev])) {
                return false;
            }
        }
        // 모두 해당하지 않으면 현재 위치는 유효한 위치
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        loc = new int[n];

        sol(0);
        System.out.println(count);
    }
}

 

위의 코드처럼 배열에 값을 먼저 넣어야만 올바르게 작동하는 것은 아니다.

 

아래 코드를 사용해도 똑같이 작동한다.

static boolean check(int row, int col) {
    for(int i = 0; i < row; i++) {
        if(arr[i] == col) return false;
        if(row - i == Math.abs(col - arr[i])) return false;
    }
    return true;
}

// sol(int row) 내부 for문
for(int col = 0; col < n; col++) {
    if(check(row, col)) {
        arr[row] = col;
        sol(row + 1);
    }
}

 

보면 알겠지만 check(row) 대신 check(row, col)을 정의해 loc[row] 대신 col 값을 이용하면, 순서는 다르지만 같은 역할을 하는 코드가 된다.

 

check(row, col)을 이용하면 배열에 값을 넣기 전 유효한 좌표인지 확인하고 나서 배열에 값을 넣고 다음 행을 재귀 호출할 수 있다.

---

대각선 확인하는 로직

두 점 A(a1, b1), B(a2, b2)가 대각선 위에 있다고 할 때, 선분 AB의 기울기는 1 또는 -1이어야 한다.

즉 기울기의 절댓값이 1이어야 한다.

기울기의 절댓값: |(b2 - b1) / (a2 - a1)| = 1

따라서 |b2 - b1| = |a2 - a1|이면 두 점 A와 B는 대각선 위에 있다.

 

b1과 b2를 각각 loc[prev]와 loc[row]로 치환하면 왜 위의 코드처럼 if문을 작성했는지 이해가 될 것이다.

 

 

---

 

 

느낀 점

처음에는 체스판이 2차원이니까 2차원 배열을 이용한 백트래킹 방식으로 해결하려 했다.

 

백트래킹에  boolean 배열이 쓰이는 것 같아 2차원 boolean 배열을 이용했으나 원하는 결과가 나오지 않아 계속 고민했다.

 

그 당시에는 배열에 퀸의 위치를 저장하는 것이 아니라 위치 가능 구역을 저장하는 식으로 구현했었다.

 

그 결과 count값이 이상하리만치 커져서 고민 끝에 결국 구글의 힘을 빌릴 수밖에 없었다.. 감사합니다 블로거 분들

계속 확인한 결과, 이전에 배치한 퀸에 의해 위치 불가능 구역으로 지정된 칸이 현재 퀸을 배치 후 다시 제거하는 과정에서 위치 가능구역으로 변환하면서 이전에 기록했던 데이터가 침범되어 올바르지 않은 결과를 낳았음을 알았다.
애초에 올바른 풀이가 아니었던 것.
2차원 배열로도 얼마든지 풀어낼 수 있었다. 이를 간소화한 것이 1차원 배열인 것이고.

 

보니까 위의 코드처럼 1차원 배열에 위치를 저장한 뒤 이전에 저장된 좌표들과의 수학적 관계를 생각하는 방법을 알게 되어 겨우 문제를 해결할 수 있었다.

 

이번 문제를 통해 반복문을 이용해 가능한 값을 하나하나 체크하는 방식도 좋지만, 이전에 저장된 값들과의 관계를 따진 후 문제를 해결하는 방법이 중요하구나를 깨달았다.

 

그리고 백트래킹 과정 중에 이전의 기록(조건)을 현재, 다음 기록이 침범하지 않도록 주의해야 함을 배웠다.