백준 9663 N-Queen

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

백트래킹 알고리즘의 기본같은 N-Queen 문제이다.

기본적으로 한 칸에 퀸을 놓으면 같은 줄에는 퀸을 놓을 수 없으므로, 세로로 한 줄씩 내려가면서 퀸을 하나씩 놓아 보며 진행하는 방식을 선택했다.

위처럼 맨 윗줄부터 놓을 수 있는 자리라면 놓고 다음 줄로 이동하되, 더 이상 놓을 자리가 없다면 (배열 끝에 도착하면) 백트래킹을 하는 방식이다.

세로로 진행함으로써 놓을 수 있는 자리인지 검사할 때 위처럼 놓을 위치의 수직 위 방향, 왼쪽 위 대각선 방향, 오른쪽 위 대각선 방향만 검사하면 되는 장점이 있다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val plate = Array(N){ BooleanArray(N){false} }

    var answer = 0
    fun nQueen(n: Int, line: Int){
        if(n == 0){
            answer++
            return
        }

        for(i in 0 until N){
            if(check(plate, line, i, N)){
                plate[line][i] = true
                nQueen(n - 1, line + 1)
                plate[line][i] = false
            }
        }
    }

    nQueen(N, 0)
    print(answer)
}

fun check(plate: Array<BooleanArray>, v: Int, h: Int, N: Int): Boolean{
    for(i in 0 until v){
        if(plate[i][h]) return false
    }

    var i = 0
    while(v - i in 0 until N && h - i in 0 until N){
        if(plate[v - i][h - i]) return false
        i++
    }
    i = 0
    while(v - i in 0 until N && h + i in 0 until N){
        if(plate[v - i][h + i]) return false
        i++
    }

    return true
}

놓은 위치를 체크하고 검사하기 위한 이차원 Boolean 배열을 선언하였다.

백트래킹을 위한 재귀함수는 남은 퀸 개수인 n과 편의를 위해 현재 세로 몇 번째 줄인지에 대한 line 파라미터를 넣고 구현하였다.

check 함수는 현재 놓을 위치의 수직 위, 왼쪽 위 대각, 오른쪽 위 대각 방향에 퀸이 이미 있는지 체크하는 함수이다.

퀸을 모두 사용해 n이 0인 상태라면 answer을 1 증가시켰다.