[백준/BOJ] 9663번: N-Queen

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

9663번: N-Queen

문제

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

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

입력

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

출력

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

해설

문제 그대로 퀸 N개가 서로 공격할 수 없게 놓으면 된다.이렇게 놓기 위한 조건으로는

1. 같은 행 또는 열에 퀸이 한개만 있어야 한다.
2. 대각선 방향으로도 한개의 퀸만 있어야 한다.

위와 같이 (0, 0)의 좌표에 퀸이 있을 때 파란색으로 색칠되있는 칸에는 퀸을 놓을 수 없다.

 

(0, 0)에 퀸이 있다 가정하고 계속해서 진행해보자.

첫번째 행에는 이미 퀸이 있으므로 두번째 행으로 넘어간다.

두번째 행에는 (1, 2), (1, 3)의 칸에 퀸을 둘 수 있다.

(1, 2)에 퀸을 두개 된다면 그 다음 행인 2행에 퀸을 둘 수 없게 된다.

따라서 이 경우를 건너뛰고 (1, 3)에 퀸을 놔보자.

(2, 1)의 칸에 퀸을 둘 수 있다.

하지만 (2, 1)에 퀸을 두고 나면, 마지막 행인 3행에 퀸을 둘 수 없게 된다.

 

따라서 맨 처음으로 돌아가 첫번째 행의 퀸의 위치를 옮겨준다.

위 과정을 계속하다보면, 다음과 같이 모든 퀸이 공격을 할 수 없는 경우가 나온다.

N이 4일 때, 모든 퀸이 서로 공격할 수 없도록 두는 방법은 위의 두가지가 끝이다.

 

이제 이를 구현하는 방법을 알아보자.

위의 설명을 읽어가면 재귀를 써야 한다는 것을 알 수 있다.

재귀부분의 코드를 살펴보면 다음과 같다.

private fun nQueen(depth: Int) {
    val lastCol = chess.size - 1

    if(promising(depth)) {
        if(depth == lastCol) count++
        else {
            for(j in 1 until lastCol + 1) {
                chess[depth + 1] = j
                nQueen(depth + 1)
            }
        }
    }
}

promising 함수는 퀸을 놓을 수 있는지 확인하는 함수로 밑에 적을 것이다.

퀸을 놓을 수 있을 때, 이 위치가 열의 마지막이라면 모든 퀸을 다 놓은 것이므로 count를 증가시켜준다.

그게 아니라면, 그 다음에 놓을 수 있는 있는지를 검사하기 위해 재귀 함수를 실행시켜준다.

 

이제 promising 함수를 확인해보자.

private fun promising(depth: Int): Boolean {
    var idx = 1
    var check = true

    while(idx < depth && check) {
        if(chess[idx] == chess[depth] || abs(chess[depth] - chess[idx]) == abs(depth - idx)) check = false
        idx++
    }

    return check
}

• chess[idx] == chess[depth]
  - 퀸이 이 열에 놓일 수 있는지를 확인한다.
• abs(chess[depth] - chess[idx]) == abs(depth - idx)
  - 대각선 방향으로 또 다른 퀸이 없는지를 확인한다.

전체적인 코드는 다음과 같다.

소스 코드

import kotlin.math.abs

private lateinit var chess: IntArray
private var count = 0

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    chess = IntArray(n + 1)
    nQueen(0)
    println(count)
}

private fun nQueen(depth: Int) {
    val lastCol = chess.size - 1

    if(promising(depth)) {
        if(depth == lastCol) count++
        else {
            for(j in 1 until lastCol + 1) {
                chess[depth + 1] = j
                nQueen(depth + 1)
            }
        }
    }
}

private fun promising(depth: Int): Boolean {
    var idx = 1
    var check = true

    while(idx < depth && check) {
        if(chess[idx] == chess[depth] || abs(chess[depth] - chess[idx]) == abs(depth - idx)) check = false
        idx++
    }

    return check
}