[백준] no9663:N-Queen

문제

N개의 퀸을 N x N의 칸 안에 경로가 겹치지 않도록 모두 배치할 수 있는 경우의 수를 구하시오

* 여기서 퀸은 체스의 퀸으로, 상하좌우방향의 모든 칸을 갈 수 있다.

---

원리

백트래킹(Back Tracking) 알고리즘

: 해를찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

예시 (펼치기)

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

다음과 같이 한 칸씩 돌면서 => 놓은 말이 이동 가능한 거리를 제외 하고 => 남은 칸 중 칸 한씩 채워보 것을 반복

=> N개의 말을 놓게 되면 경우의 수 count

조건1. 어떻게 재귀 할 것인지

즉, N x N인 이중배열 안의 각 칸에 순차적으로 퀸을 넣어가며, N개의 퀸을 모두 놓을 수 있는 해를 모두 구하는 방법

또한, 여기서 이중배열 대신 1차원 배열로도 해결이 가능하다.

=> 각 원소의 Index를 열(column)라고 생각하고, 원소의 값을 행(low)으로 생각하여 재귀를 반복한다.

    private static void check(int nQueen) {
        // N개를 채운 상태면 count 증가 후 스답
        if(nQueen == N) {
            count++;
            return;
        }

        for(int i = 0 ; i < N ; i++) { // N개까지 확인할 것이며,
            arr[nQueen] = i;
            if(possibility(nQueen)) check(nQueen + 1); // N개 중 현재 순서의 퀸을 놓을 수 있다면, 다음 퀀 놓을자리를 다시 체크
        }
    }

 

조건2. 어떻게 칸의 중복을 파악할 것인지

1) 같은 행에 존재하는 경우 = 해당 열의 행과 방문한 열의 행이 일치하는 경우

for(int now = 0 ; now < column ; now++) {
	if(arr[column] == arr[now]) return false;
}

2) 대각선상에 놓이는 경우 = 열의 차와 행의 차가 같은 경우

for(int now = 0 ; now < column ; now++) {
    if(Math.abs(column - now) == Math.abs(arr[column] - arr[now])) return false;
}

3) 만약 1과 2에 해당되지 않고 모두 통하면 = true (성공) 

---

나의 코드

(이 코드는 레퍼런스 코드와 동일하며, 해당 코드에 대한 이해를 중점적으로 작성함)

import java.io.*;

public class no9663 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, count;
    private static int[] arr;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        check(0); // check의 int형 변수 = 0~N번째으 퀸

        System.out.println(count);
    }

    private static void check(int nQueen) {
        // N개를 채운 상태면 count 증가 후 스답
        if(nQueen == N) {
            count++;
            return;
        }

        for(int i = 0 ; i < N ; i++) { // N개까지 확인할 것이며,
            arr[nQueen] = i;
            if(possibility(nQueen)) check(nQueen + 1); // N개 중 현재 순서의 퀸을 놓을 수 있다면, 다음 퀀 놓을자리를 다시 체크
        }
    }

    /**
     * 상하좌우 방향의 모든 칸에 대해서 가능/불가능 확인 용도의 메소드
     */
    private static boolean possibility(int column) {
        for(int now = 0 ; now < column ; now++) {
            if(arr[column] == arr[now]) return false;
            else if (Math.abs(column - now) == Math.abs(arr[column] - arr[now])) return false;
        }
        return  true;
    }
}

 

---

레퍼런스

참고링크 : https://st-lab.tistory.com/118