[2023-04-12] 9663번 N-Queen(Kotlin)

 

 

문제 링크: https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

어떻게 접근해야 할지 감이 오지 않았습니다.

 

 

일단 규칙을 찾아보기 위해 그림을 그렸습니다.

 

 

// 0 0 x 0      N = 4
// x 0 0 0  
// 0 0 0 x
// 0 x 0 0

// 0 0 0 x 0    N = 5
// 0 x 0 0 0
// 0 0 0 0 x
// 0 0 x 0 0
// x 0 0 0 0

 

 

처음에는 x값, y값을 Pair로 가지는 배열을 만드려고 했습니다. ex)  Array<Pair<Int, Int>>()

 

경우의 수들을 생각해보다가 그럴 필요가 없다는 것을 깨달았습니다.

 

 

// 0 0 x 0     2 4 1 3
// x 0 0 0
// 0 0 0 x
// 0 x 0 0

// 0 0 0 x 0   5 2 4 1 3
// 0 x 0 0 0
// 0 0 0 0 x
// 0 0 x 0 0
// x 0 0 0 0

 

하나의 배열을 이용할 때 y값만을 이용하면, 하나의 배열로 처리를 할 수 있다는 것을 깨달았습니다.

 

퀸이 잡아먹을 수 있는 구역은 y값에 따라 달라지기 때문입니다.

 

더 나아가 규칙을 고민해봤습니다.

 

 

인접한 요소의 y값 차이는 1 이상이여야 합니다.

 

 

ex)  잡아 먹히는 경우

// x 0  0 x
// 0 x  x 0

// x x  0 0
// 0 0  x x

 

 

거리 차이가 2인 요소의 y값 차이는 0과 2 둘 다 아니여야 합니다.

 

 

ex) 잡아 먹히는 경우

// x 0 0
// 0 0 0
// 0 0 x

// x 0 x
// 0 0 0
// 0 0 0

 

 

거리 차이가 3인 요소까지 생각을 해본 결과 다음과 같은 규칙을 찾을 수 있었습니다.

 

 

// 0 x   y값 차이가 1이 되면 안됨
// x 0

// x 0 0   y값 차이가 2가 되면 안됨
// 0 0 0
// 0 0 x

// x 0 0 0   y값 차이가 3이 되면 안됨
// 0 0 0 0
// 0 0 0 0
// 0 0 0 x

 

dfs에서 visit 배열을 만들어, 방문했던 요소는 제외할 것이므로

 

 

같은 줄에 존재하는 경우 (y값 차이가 0인 것) 는 고려하지 않아도 됩니다.

 

 

 

첫 번째 시도입니다.

 

package twelvethDay
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n){0}
    val visit = Array(n+1){false}
    var count = 0
    fun dfs(num: Int){
        if (num == n){ // 배열을 끝까지 채웠을 때
            var isPossible = true
            for (index in arr.indices){ 
                var i = 1
              
                while(true){
                    if (index + i > arr.size - 1)
                        break
                    // 두 요소의 y값 차이가, 두 요소의 거리와 같으면 false
                    if (Math.abs(arr[index] - arr[index+i]) == i)
                        isPossible = false
                        
                    i ++
                }
            }
            // true 일 때만 count 세기
            if (isPossible){
                count++
            }
            return
        }
        for (index in 1..n){
            if (!visit[index]){
                visit[index] = true
                arr[num] = index
                dfs(num+1)
                visit[index] = false
            }
        }
    }
    dfs(0)
    println(count)
}

 

 

출력값 예시대로 나오는 것을 확인했지만, 시간 초과가 떴습니다.

 

규칙을 검사하는 부분을 수정해야 했습니다.

 

 

 

다음과 같이 코드를 작성하였습니다.

 

 

package twelvethDay
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n){0}
    val visit = Array(n+1){false}
    var count = 0
    
    fun dfs(num: Int, prevNum: Int){ // 인자로 이전 num을 받습니다.
        if (num == n){
            count ++
            return
        }
        for (value1 in 1..n){
            if (!visit[value1]){
            	
                var tag = false
                // 이전 배열의 num 부터 0까지 반복하여
                for (value2 in prevNum downTo 0) {
                	// 넣을 값인 value1과, 이전 배열 요소들을 비교합니다.
                    if (Math.abs(value1 - arr[value2]) == num - value2) {
                        tag = true
                        break
                    }
                }
                
                // 비교한 값이 두 요소의 거리차와 같다면 continue
                if (tag)
                    continue
                    
                visit[value1] = true
                arr[num] = value1
                
                dfs(num+1, num) // 이전 배열 위치인 num을 넘겨줍니다.
                
                visit[value1] = false
            }
        }
    }
    dfs(0, -1)
    println(count)
}

 

 

 

 

 

 

백트래킹 관련 문제인 것을 알고있어서 풀 수 있었다고 생각합니다.

 

 

비슷한 문제들을 많이 풀어보며 감각을 익혀야 할 것 같습니다.