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

문제 내용

문제

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

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

입력

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

출력

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

예제 입력	예제 출력
8	92

문제 풀이

처음에 문제를 보고 체스의 퀸이 어떻게 움직이는지 몰라서 검색을 했었다.. ^^,,, 퀸은 위 그림처럼 가로 세로 대각선으로 칸 수의 제한을 받지 않고 움직인다. 

그럼 NQueens는 어떻게 있어야 된다는 말일까? N = 4일때, 어떻게 나올지 그려보면 아래 처럼 나타난다.

N = 4일때, N-queen

그럼 우리가 여기서 고려해봐야 할건, 가로에 하나씩 비치 되어야되고, 근데 그게 세로줄에도 내가 놓을 퀸 하나만 있어야되고, 대각선에도 내가 놓을 퀸 하나만 있어야 된다.

쉽게 생각해보면, 어쨋든 가로 줄에 하나씩은 queen 을 둔다 생각하고 위치한 자리에 세로 줄에 퀸이 있는지, 대각선에 퀸이 있는지 확인하고 겹치는게 없다면 그자리에 queen을 두면된다.

이렇게 끝줄까지 가는걸 성공했다면 모든 줄에 queen을 잘 비치 했다는 얘기이다. 이 경우에는 count를 1증가 시켜주고, 재귀가 끝이 나면 출력을 하면 된다. 

그럼 위의 생각을 코드로 어떻게 옮길지 설계해보자.

1) 가로에 하나만 비치해야된다. 

재귀의 depth를 가로로 생각하고 풀이한다. 재귀를 가로 줄의 수인 N만큼만 돌도록 한다.
→ depth가 n이 되면 return(종료)시킨다. 

2) 세로에 하나만 비치해야된다.

BooleanArray에 방문했는지 안했는지 확인하자. Visited[세로줄의 좌표] = true(세로줄에 이미 있음), false(세로줄에 놓을수있음)

3) 대각선에 하나만 비치해야된다. (대각선은 두방향임)

BooleanArray에 방문했는지 안했는지 확인하면, O(1) 시간으로 체크할 수 있지 않을까? 대각선도 Boolean 배열을 만들자.

Plus : r+c, Minus : r-c

대각선끼리의 공통점이 보이는가? 한 대각선은 r+c 값이 대각선 내에서 같고, 반대 대각선은 r-c 값이 대각선 내에서 같다. 

그러면, 어떤 지점에 도착했을때 그 값의 r+c 값에 온적이 있는지, r-c 값에 온적이 있는지 2)와 함께 확인해보면, 그 위치에 둘 수 있는지 확인할 수 있다! 대신 범위는 2 * n 까지로 두고 r-c의 경우 배열 범위에 맞추기 위해 n을 더해준다. 

4) N-queen은 몇개 만들어지는지 출력한다!

위 조건을 만족하고 종료 조건까지 도달했다면, N-queen이 하나 만들어졌다는 것이다. 따라서, 이때 count의 값을 1증가 시켜준다. 또한 모든 재귀가 종료되었을때 print(count)를 해주어 결과를 확인한다.

결론

다른 사람들의 풀이를 보았을때, 대부분이 for문을 돌려 한줄 한줄, 대각선과 가로세로에 있는지 확인하는 모습을 볼 수 있었다! 하지만, boolean 배열로 방문 여부를 체크해서 존재 여부를 확인한다면 더 빠르게 풀 수 있다! 대략 시간 2배정도 차이가 난다 

</>̆̈ 코드

import java.io.BufferedReader
import java.io.InputStreamReader

private val n = BufferedReader(InputStreamReader(System.`in`)).readLine().toInt()
private val chessBoard = Array(n) {IntArray(n)}

private val visited = BooleanArray(n)
private val crossMinus = BooleanArray(2 * n)
private val crossPlus = BooleanArray(2 * n)

private var cnt = 0

fun main() {
    playChess(0)
    print(cnt)
}

private fun playChess(r: Int) {

    if (r == n) {
        cnt += 1; return
    }

    for (c in 0 until n) {
        if (!checkChess(r, c)) {
            visited[c] = true; crossMinus[n+r-c] = true; crossPlus[r+c] = true
            playChess(r + 1)
            visited[c] = false; crossMinus[n+r-c] = false; crossPlus[r+c] = false
        }
    }
}

private fun checkChess(r: Int, c: Int) = visited[c] || crossMinus[n+r-c] || crossPlus[r+c]

링크

9663번: N-Queen