프로그래머스[programmers] - N-Queen(Kotlin)[LV2]

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

문제 풀이

전형적인 백트래킹 문제이다.

2차원 배열을 사용해서 풀기보다는 조금 특별하게 풀고 싶었다.

따라서 Queen이라는 데이터클래스를 가지는 배열을 통해서 각자의 위치에 따라 공격할 수 있는 여부를 따지고 싶었다.

그래서 n만큼의 depth를 탐색하는 재귀함수를 작성해서, Queen의 column위치를 계속해서 조정했다.

배열에 Queen을 넣고, 해당 퀸의 추가가 적절한 추가인지 검사하고, 재귀함수를 진행했다.

이렇게 하면 재귀함수의 호출을 줄일 수 있다고 판단했고, 실제로 재귀함수의 호출이 적어져서 깊이가 줄어들었다.

하짐잔 재귀함수를 적게 호출하는 대신 checkAttack()이라는 함수를 호출했지만 재귀함수의 호출의 깊이가 줄어드는 것이 더 이득이라고 판단했다.

checkAttack()은 각각 세로, 대각선에 위치하는 체크말 수를 카운트한다.

가로를 체크해도 되지 않는 이유는 가로는 항상 다르게 위치시키기 때문이다.

본인 빼고 세로, 대각선에 위치하는 말이 있다면 size가 2이므로 false를 반환한다.

이렇게 재귀함수를 호출하기 전에 적절한 삽입일 경우 재귀를 호출하고, 깊이가 n일 경우 경우의 수를 +1 해준다.

 

 

전체 코드

import kotlin.math.*
class Solution {
    
    var graph : ArrayList<Queen> = arrayListOf()
    var answer =0
    data class Queen(var row : Int, var col : Int)    
    fun solution(n: Int): Int {
        nQueen(n,0)
        return answer
    }
    
    fun nQueen(n : Int, depth : Int){                
        if(depth==n){
            answer++
            return
        }       
        for(col in 0 until n){
            graph.add(Queen(depth,col))
            if(!checkAttack())
                nQueen(n,depth+1)
            graph.remove(Queen(depth,col))
        }
    }
    fun checkAttack() : Boolean{
        for(queen in graph){            
            val col = graph.filter{it.col==queen.col}
            val up = graph.filter{(queen.col-it.col) == (queen.row-it.row) || (it.col-queen.col)==(queen.row-it.row)}
            if(col.size>=2 || up.size>=2)
                return true
        }
        return false
        
    }
}