[백준] [9663] N-Queen (JAVA) (백트래킹) (gold 4)

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

9663번: N-Queen

---

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

※ JAVA 코드 (N-Queen)

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

public class Main {
    public static int N;
    public static int[] map;
    public static int dap;

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[16];

        N = Integer.parseInt(br.readLine());

        solve(0);
        System.out.println(dap);
    }
    static boolean isPossible(int i) {
        for (int j = 0; j < i; j++) {
            int tmp;

            //같은행, 같은열은 pass
            if (map[j] == map[i]) return false;

            if (map[i] > map[j]) tmp = map[i] - map[j];
            else tmp = map[j] - map[i];

            if(tmp == (i - j)) return false;
        }
        return true;
    }

    static void solve(int i) {
        if (i == N) dap++;
        else {
            for (int j = 0; j < N; j++){
                map[i] = j;
                if (isPossible(i)) solve(i + 1);
            }
        }
    }
}

---

※ 생각정리

 

N-Queen은 백트래킹 문제의 꽃이자 시작이며 백트래킹을 사용하는 의미있는 문제라고 생각한다.

 

문제에 주어진 내용(단서)을 가지고 먼저 문제를 이해하고 들어가야한다.

 

1) N x N 크기가 주어지며 이로 유추 할 수 있는 것은 정사각형모양이라는 것이다. 또한 N의 크기는 최대 14 까지의 크기를 가지고 있다.

 

2) ☆[중요]☆ 1번에서 추가적으로 알면 좋은 내용은 해당 문제에서 2차원 배열은 1차원배열로 표현해 물면 더 쉽게 풀 수 있다.

여기서 잠깐 ???를 남발하시는 분들을 위해 어떻게 2차원이 1차원이 될 수 있는지에 대한 그림이 있다.

 

 

 

3) {4, 2, 5, 3, 1} 숫자가 적힌 순서가 행 숫자가 적힌 인덱스가 열이 될 수 있다. 즉 int[] map = {4, 2, 5, 3, 1} 이라는 1차원 배열을 만든다면 위 그림과 같이 2차원 배열이 만들어질 수 있다.

 

4) 순서는 다음과 같다

1. 맨처음 1행에 임의의 자리에 퀸을 둔다

2. 두번째 2행에 가능한 자리에 퀸을 둔다

3. N번째 행까지 다음을 반복하고 중간에 안된다면 바로 그 전 상태로 돌아간다.

 

위의 4번 과정을 그림으로 표시하면 어떻게 될까 (둘 수 없는 자리는 회색처리)

 

[설명] 1행 4열 자리에 퀸을 두고 다음 퀸자리를 탐색한다. 2행에 퀸을 둘 수 있는 자리는 1열과 2열 두자리가 될 수 있으며, 해당 분기때 재귀를 타게 하여 1열을 통한 재귀가 실패했을 경우 2열 재귀가 실행되도록 돌아와 주어야한다. (이게 백트래킹)

이해가 안갈 수 있으니 더 그림을 그려보며 진행해보자.

 

[설명] 3행까지 퀸을 채워 보았다. 이때도 2개의 경우가 나올 수 있으니 분기가 나뉘게 되며, 끝까지 진행해보겠는데 이후 4행과 5행에 퀸을 넣을 수 있는 경우는 1가지 씩밖에 없으며 해당 위치에 퀸을 넣어도 모든 조건을 만족하기 때문에 N개의 퀸을 넣을 수 있다.

 

 

[설명] 이렇게 N-Queen을 완성했으니 바로 이전 분기로 돌아가 다음 분기에도 N-Queen을 만들 수 있는지 확인 해보겠다.

[설명] 위 그림을 보면 4행, 5행에 퀸을 넣을 수 있는 자리는 각 1자리 뿐이지면 열이 겹치는 상황이므로 4행까지는 퀸을 둘 수 있지만 5행에 퀸을 둘 수 없다.

 

[설명] 해당 분기도 모두 끝났으니 이전 분기로 또 돌아간다. (다시 한번 말하지만 이렇게 돌아가기기 때문에 백트래킹이라고 한다) 2행에서 만들어졌던 분기로 돌아가 보자

 

아까는 2행 1열 자리를 선택했지만 이번엔 2행 2열에 자리에 퀸을 두었다. 3행에 자리는 1개뿐이니 바로 채워보자

 

 

4행, 5행에 각각 1자리씩이 있으며 둘다 퀸으로 채워도 문제가 없으므로 또, N-Queen을 완성할 수 있게 된다.

 

위 예제는 4열부터 시작했지만, 실제로는 1행 1열부터 시작하여 1행 N열까지 반복하며 재귀를 호출해야한다.

각 열당 최대 N - 1개의 재귀를 타게 됩니다(중요하지 않으므로 그냥 넘어가셔도 됩니다)

 

 

문제나 해설 관련 추가 질문은 따로 연락주세요~

 

- 새벽코딩 -