[백준] 9663. N-Queen (Kotlin)

문제 : www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

import java.lang.Math.abs
import java.util.*

var n = 0
var sum = 0
var col = Array(15){0}

fun main(args : Array<String>) = with(Scanner(System.`in`)){
    n = nextInt()
    dfs(0)
    println(sum)
}

fun dfs(x : Int){
    if(x == n) sum++
    else{
        for(i in 0 until n){
            col[x] = i // x 번째 열의 i 번째 행
            if(check(x))
                dfs(x+1) // 퀸을 놓았다면 다음열로 (열체크 필요 X)
        }
    }
}

fun check(level : Int) : Boolean{
    for(i in 0 until level)
        if(col[i] == col[level] || abs(col[level] - col[i]) == level - i) return false
    // 같은 행에 있거나 대각선에 있으면 false
    return true
}

처음에 이차원 배열로 해결하려다가 헤맨 문제이다.

배열의 인덱스를 열, 값을 행으로 놓고 풀었다.

 

또한 행과 열을 체크하는 것은 어렵지 않았는데, 대각선을 체크하는데 헤맸다.

대각선은 현재위치에서 x축,y축을 둘다 +-1 씩 한 값이기 때문에

x,y축의 차가 현재위치의 x,y축의 차와 같을수 밖에 없는 점을 이용하여 해결하였다.