[Programmers] Lv2. N-Queen(kotlin)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12952?language=kotlin

 

 

예시

https://school.programmers.co.kr/learn/courses/30/lessons/12952?language=kotlin

 

 

풀이

• N-Queen은 백트래킹의 대표적인 문제로 y축을 하나씩 내려가면서 x축을 한번 순회하여 Queen이 놓아질 수 있는 곳을 찾는 문제입니다.
• 하나씩 탐색하면서 찾아도 되지만 수학적으로 좌표를 활용하여 문제를 풀면 빠르게 풀 수 있습니다.
• 대각선끼리도 같은 라인에 Queen이 있으면 안되는데 좌표의 기울기나 규칙을 통해서 같은 대각선인지 아닌지 알 수 있습니다.
• 오른쪽 아래로 향하는 대각선에서 y-x 값이 동일한 좌표는 같은 대각선 상에 존재합니다.
• 마찬가지로 왼쪽 아래로 향하는 대각선끼리는 y+x 값이 동일합니다.
• 따라서 y좌표는 하나씩 내려가면서 x좌표만 0부터 n-1까지 순회하여 dlist (down list), rdlist(right down list) , ldlist(left down list) 에 추가하고 이미 좌표값이 포함되어 있으면 건너뛰면 됩니다.

class Solution {
    var answer = 0
    
    fun backtraking(n: Int, y: Int, dlist: List<Int>, rdlist: List<Int>, ldlist: List<Int>){
        if(n == y){
            answer++
            return
        }
        
        (0 until n).forEach{ i ->
            if(dlist.contains(i).not() && rdlist.contains(y-i).not() && ldlist.contains(y+i).not()){
                backtraking(n, y+1, dlist + listOf(i), rdlist + listOf(y -i), ldlist + listOf(y + i))
            }
        }
    }
    
    fun solution(n: Int): Int {
        backtraking(n,0,listOf<Int>(), listOf<Int>(), listOf<Int>())
        return answer
    }
}

 

 

 

참고

• 함수형 프로그래밍 언어인 kotlin의 특성에 맞게 함수를 많이 익히자 😽
• https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/contains.html

contains - Kotlin Programming Language