[프로그래머스] N-Queen with Kotlin

문제

가로, 세로의 길이가 n인 체스판이 있다.

체스판 위의 n개의 퀸이 서로 공격할 수 없도록 배치했을 때, 배치할 수 있는 경우의 수 반환

 

풀이 과정

1. n개의 퀸을 배치해야되기 때문에 각 열에는 무조건 하나의 퀸이 있어야 함

2. 위에서부터 각 열의 칸마다 퀸을 배치하여 서로 공격 가능하면 pass 불가능하면 다음 열 탐색

3. 위에서부터 배치하기 때문에 퀸의 공격은 위로만 체크

 

코드

class Solution {
    var answer = 0
    fun solution(n: Int): Int {
        if(n == 1) return 1
        
        val chessboard = Array(n){Array(n){0}}
        
        dfs(chessboard, 0)
        
        return answer
    }
    
    fun dfs(chessboard: Array<Array<Int>>, line: Int){
        // line이 보드판을 넘어가면 Q를 전부 할당했다는 뜻
        if(line >= chessboard.size){
            answer++
            return
        }
        
        // 탐색은 현재 행의 상단만, 아래는 Q가 없음
        val dx = arrayOf(-1, -1, -1)
        val dy = arrayOf(0, -1, 1)
        
        for(space in chessboard[line].indices){
            val board = Array(chessboard.size){chessboard[it].copyOf()}

            //가로 세로 대각선 확인
            var attack = false
            for(i in 0..2){
                var row = line + dx[i]
                var col = space + dy[i]
                while(true){
                    // 보드판을 벗어나면 종료
                    if(row < 0 || row >= board.size || col < 0 || col >= board.size){
                        break
                    }
                    // 퀸을 발견하면 종료
                    if(board[row][col] == 1){
                        attack = true
                        break
                    }

                    row += dx[i]
                    col += dy[i]
                }
                // 공격 가능으로 다음 탐색은 필요하지 않음
                if(attack) break
            }

            // 공격 불가 지점이면
            if(!attack){
                board[line][space] = 1
                dfs(board, line+1)
            }
            // 라인에 Q을 할당할 수 있는 칸이 없다면 재귀X
        }
    }
}