[Java] 백준 9663번 - NQueen (BackTracking)

백트래킹(BackTracking)이란? 

가능한 모든 경우의 수를 찾는데, 특정 조건을 만족한 경우한 찾는 방법 

예를 들어, nPr 같은 경우 효율성이 안나오는데 특정 조건을 만족하게(조건문을 걸어서 탐색 중지하고 이전으로 되돌아가게끔)하면 사용 가능하다. 

 

백트레킹의 유명한 예제로 N-Queen문제가 있다.  

이 문제는 SW export academy 2806번에 문제 설명이 잘 나와있으니 문제 설명은 다음 링크에서 확인하면 될 것같다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE 

SW Expert Academy

 

 

N-Queen 백준 9663번

이 문제는 그냥 생각했을 때 "2차원 배열or리스트를 사용해서 문제를 풀어야겠다!"라 생각할 수 있다. 하지만 Queen은 상하좌우(같은 열, 같은 행), 대각선에 겹치면 안되기때문에 한 행, 한 열에는 무조건 한 개의 Queen만 올 수 있다.그렇다면 우리는 굳이 2차원 배열을 사용하는 법보다, 1차원 배열을 사용하자N = 4일때 살펴보면 다음과 같이 1차원 배열을 사용할 수 있다. 

0 q 0 0              1위치                   =>           arr[] = {1, 3, 2, 0}

0 0 0 q              3위치

0 0 q 0              2위치

q 0 0 0              0위치

 

arr[] = {1, 3, 2, 0} 이 의미하는 걸 정리해보자면 ..

arr[0] = 1 :   [0][1] 위치에 Queen이 온다  /  0번째 줄(row)의 1인덱스 위치에 Queen이 온다.

 

그럼 어떻게 접근할까?

 

1. queen메서드는 타겟 줄의 idx를 다른 줄의 idx와 확인해줘야한다. 

2. 그때 확인은 상하(같은 열), 대각선에 Queen이 있는지 확인한다. <- isPossible 메서드 

3. arr는 {0, 0, 0, 0} (N=4일때) 초기화되어있고, idx를 앞에서부터 차례대로 탐색한다. 

     따라서, idx가 arr의 마지막 원소까지 세팅을 한다면 idx ++ 되므로, idx == arr.length일때 return해주며 cnt++해준다. (cnt는 arr에 Queen이 위치할 수 있는 경우의 수)

 

+ 좌우는 같은 행을 보는건데, 우리는 같은 행에 Queen이 못온다는 걸 전제로하고 1차원배열로 선언해줬의 체크하지않아도 된다.

+ 같은 대각선에 있는지 확인하는 건 열의 차 == 행의 차 를 활용하면 된다.

 

코드를 보기전에 변수 의미를 제대로 이해하고 가보자

rowIdx : 몇번째 줄인지

arr[rowIdx] : rowIdx줄에 Queen이 위치하는 인덱스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N;
    static int arr[];
    static int cnt;

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

        Queen(0);

        System.out.println(cnt);
    }

    private static void Queen(int idx) {
        if (idx == arr.length) {
            cnt++;
            return;
        }
        for (int i = 0; i < N; i++) {
            arr[idx] = i; // idx번째 줄(row)에 i 위치에 놓기

            if (isPossible(idx)) {    // idx번째 줄(row)이 가능한지
                Queen(idx + 1);
            }
        }
    }

    private static boolean isPossible(int rowIdx) {
        // 같은 열에 없는 지 확인
        for (int i = 0; i < rowIdx; i++) {
            if (arr[rowIdx] == arr[i]) {
                return false;
            }

            // 대각선 확인 - arr[rowIdx] : rowIdx줄의 Queen위치, rowIdx : col index  -> 행, 열 차가 같으면 대각선
            else if (Math.abs(rowIdx - i) == Math.abs(arr[rowIdx] - arr[i])) {
                return false;
            }
        }
        return true;
    }


}