[백준] 9663번 - N-Queen (Java)

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

9663번: N-Queen

 

<문제 분석>

백트래킹의 대표 문제이다.

퀸은 상하좌우 대각선으로 거리제한 없이 움직일 수 있다. 그 동선에 걸리지 않도록 다른 퀸을 N개 배치를 하는 경우의 수를 구하는 문제이다. 각 행별로 놓을 수 있는 위치가 발견되면 재귀호출을 해주고, N개 만큼 배치가 되었다면 count+1을 해준다.

 

* 두가지 문제

1. 재귀호출을 어떤 방식으로 할 것인가

2. 퀸을 놓을 수 있는 위치인지 어떻게 판단할 것인가

 

* 체스판의 퀸을 일차원 배열로 표현하는 법

1. 배열의 인덱스를 체스판의 열로 생각한다.

2. 배열에 들어가는 숫자를 체스판의 행으로 생각한다.

 

왼쪽부터 (행, 열) = (0, 1), (1, 3), (2, 0), (3, 2) 이다.

[1, 3, 0, 2]로 표현할 수 있다. 즉, 행(row)은 배열의 인덱스, 열(col)은 배열에 들어가는 값이다. (0 ~ N-1)

※ 이해가 어려워서 복도식 아파트의 각 층(행)마다 호실(열)이 있는 것으로 대입했다.

 

<코드 구현>

import java.util.Scanner;


//[백준] 9663번 - N-Queen (Java)

public class Main {
    static int N;
    static int arr[];
    static int count = 0;
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];
    }

    public void dfs(int depth) {
        // 1. 종료조건
        if (depth == N) { // depth가 N가 같아지면 탐색 종료
            count++; // N개의 queen을 다 놓은 것이므로 +1 증가
            return;
        }
        // 2. 함수본체
        for (int i=0; i<N; i++) { // i : 체스판의 열
            // depth : 체스판의 행
            arr[depth] = i; // depth행 i열에 퀸을 놓자

            // depth행 i열에 퀸을 놓을 수 있는지 확인하는 함수
            // 노드의 유망성을 확인하는 백트래킹 기법
            if (checkQueen(depth)) {
                dfs(depth+1); // 한 행을 증가시켜서 탐색한다.
            }
        }
    }

    public boolean checkQueen(int row) {
        // depth(row)를 증가시키면서 확인하기 때문에 같은 열과 대각선만 확인하면 된다.
        for (int i=0; i<row; i++) {
            // 행은 다르지만 같은 열에 퀸이 있어서 놓을 수 없다.
            if (arr[row] == arr[i]) {
                return false;
            }
            // 대각선에 놓인 퀸이 있는지 체크
            // '행의 차'와 '열의 차'가 같으면 대각선에 놓여있는 경우다.
            else if (Math.abs(row - i) == Math.abs(arr[row] - arr[i])) {
                return false;
            }
        }
        return true;
    }

	public void Solve() {
        dfs(0);
        System.out.println(count);
	}
    
	public static void main(String[] args)
	{
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}

 

<제출 결과>