백준 9663번 with Kotlin

N-Queen 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

10 초

128 MB

45388

23718

15531

51.637%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

 

이문제 처음에는 2차원 배열로 풀려고 했는데 메모리 초과가 나서 검색을해서 일차원 배열에 index를 행으로 하고 value를 col로 하는 아이디어를 얻어서 풀었다.. 하.. 코테에 이런문제가 나온다면 이런 생각을 할 수 있었을까? ㅠㅠ

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
 
 
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
val n = readLine()!!.toInt()
var chessBoard = Array(n,{BooleanArray(n,{false})})
 
var count = 0
fun main()=with(br){
 
    Nqueen(0)
    var happy = chessBoard
    chessBoard = Array(n,{BooleanArray(n,{false})})
    /*
    for(k in 0 until n){
        for(j in 0 until n)
            print("${chessBoard[k][j]} ")
        println()
    }
 
 
    for(k in 0 until n) {
        for (j in 0 until n)
            print("${happy[k][j]} ")
        println()
    }
    */
    println("$count")
    bw.flush()
    bw.close()
}
fun Nqueen(r:Int){
    if(r==n){
        count++
        return
    }
    var key = true
    var once = true
    var temp  = Array(n,{BooleanArray(n,{false})})
    for(i in 0 until n){
        if(key) {
            if(once) {
                once=false
                for (k in 0 until n) {
                    for (j in 0 until n)
                        temp[k][j] = chessBoard[k][j]
                }
            }
        }
        else{
            key = true
            for(k in 0 until n){
                for(j in 0 until n)
                    chessBoard[k][j]= temp[k][j]
            }
        }
        if(!chessBoard[r][i]) {
            key = false
            chessBoard[r][i] = true
            row(r, i)
            col(r, i)
            diagonal(r, i)
            /*
            println("r: $r , i: $i")
            for(k in 0 until n){
                for(j in 0 until n)
                    print("${chessBoard[k][j]} ")
                println()
            }
            println()
            */
 
            Nqueen(r+1)
        }
    }
}
 
fun row(r:Int,i:Int){
    for(k in 0 until n){
        chessBoard[k][i]=true
    }
}
 
fun col(r:Int,i:Int){
    for(k in 0 until n){
        chessBoard[r][k]=true
    }
}
 
fun diagonal(r:Int,i:Int){
    var r = r
    var i = i
    for(k in 0 until n){
        var dx = r+k
        var dy = i+k
        if(dx>n-1 || dy>n-1)
            break
        else{
            chessBoard[dx][dy]=true
        }
    }
 
    for(k in 0 until n){
        var dx = r-k
        var dy = i-k
        if(dx<0 || dy<0)
            break
        else{
            chessBoard[dx][dy]=true
        }
    }
    for(k in 0 until n){
        var dx = r+k
        var dy = i-k
        if(dx>n-1 || dy<0)
            break
        else{
            chessBoard[dx][dy]=true
        }
    }
 
    for(k in 0 until n){
        var dx = r-k
        var dy = i+k
        if(dx<0 || dy>n-1)
            break
        else{
            chessBoard[dx][dy]=true
        }
    }
}

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.abs
 
 
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
val n = readLine()!!.toInt()
var chessBoard = Array(n){1000}
var count = 0
fun main()=with(br){
    Nqueen(0)
    println(count)
    bw.flush()
    bw.close()
}
fun Nqueen(r:Int){
    if(r==n){
 
        count++
        return
    }
   for(i in 0 until n){
       chessBoard[r]=i
       if(check(r)){
           Nqueen(r+1)
       }
   }
}
 
fun check(go:Int):Boolean{
    for(i in 0 until go){
        if(chessBoard[i]==chessBoard[go] || (abs(i-go)+abs(chessBoard[i]-chessBoard[go])==2*(go-i)))
            return false
    }
    return true
}
 
 

아이디어를 참고해서 짠 코드. 생각하나가 알고리즘을 이렇게 좋게 만든다.