[백준][코틀린][9663] N-Queen

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

9663번: N-Queen

문제 풀이

1. 체스 판에 놓여진 퀸을 기준으로 가로/세로/대각선 방향으로 공격할 수 있기 때문에 다른 퀸을 놓을 수 없다.

2. 따라서 퀸을 하나 놓으면 놓여진 행에는 다른 퀸을 놓을 수 없기 때문에 탐색을 할 필요가 없다.

3. 놓여진 퀸의 열을 탐색하여 놓을 수 있는 열이 있는 지 확인 한다.

4. 대각선의 경우 오른쪽 위에서 부터 시작하는 대각선과 왼쪽 위에서 부터 시작하는 대각선이 있다.

5. 탐색하는 행을 기준으로 위쪽 대각선들만 탐색한다. 아래쪽의 경우 다음 행에서 탐색이 되기 때문에 위쪽만 탐색해도 전체 탐색이 가능하다.

6. 대각선 탐색 시 아래와 같이 row + col 의 값을 채운다.

 

7. 아래의 붉은 네모 칸 3을 기준으로 대각선 탐색을 할 수 있는 Index 규칙은 다음 과 같다. 

- 오른쪽 위 : row + col

- 왼쪽 위 : Math.abs(row - col) : 이렇게 정할 경우 파란색 네모칸 1을 기준으로 할 때 오른쪽 위의 Index 도 동일하게 1이 되어 구분을 할 수 없다. 따라서 왼쪽 위의 경우 N 을 더해서 Index 중복을 피한다.

8. 0번째 행 부터 DFS 를 이용하여 반복 탐색한다.

코드

import java.io.*

private var result = 0

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()

    val visit = BooleanArray(N) { false } // 같은 열에 퀸이 있는 지 확인하는 배열
    val rightVisit = BooleanArray(N * 2) { false } // 놓여 있는 퀸의 오른쪽 대각선 위에 놓을 수 있는 지 확인하는 배열
    val leftVisit = BooleanArray(N * 2) { false } // 놓여 있는 퀸의 왼쪽 대각선 위에 놓을 수 있는 지 확인하는 배열

    dfs(N, 0, visit, rightVisit, leftVisit)
    println(result)
}

private fun dfs(N: Int, row: Int, visit: BooleanArray, rVisit: BooleanArray, lVisit: BooleanArray) {
    if (row == N) {
        result++
        return
    }

    for (i in 0 until N) {
        if (check(N, row, i, visit, rVisit, lVisit)) {
            visit[i] = true
            rVisit[row + i] = true
            lVisit[N + row - i] = true
            dfs(N, row + 1, visit, rVisit, lVisit)
            visit[i] = false
            rVisit[row + i] = false
            lVisit[N + row - i] = false
        }
    }
}

private fun check(N: Int, row: Int, col: Int, visit: BooleanArray, rVisit: BooleanArray, lVisit: BooleanArray): Boolean {
    if (visit[col]) return false
    if (rVisit[row + col]) return false
    if (lVisit[N + row - col]) return false

    return true
}