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

프로그래머스

문제 해석

N-Queens 문제는 N개의 퀸을 NxN 체스판에 배치하되, 서로가 공격하지 못하도록 배치하는 방법의 수를 찾는 문제이다.

---

풀이 방법

import kotlin.math.abs

class Solution {

    fun solution(n: Int): Int {
        var answer = 0

        fun checkQueen(cols: IntArray, row: Int) {
            if (row == n) {
                answer++
                return
            }
            
            fun isLocateQueen(row: Int, col: Int): Boolean {
                for (i in 0 until row) {
                    if (cols[i]== col|| abs(row-i) == abs(col-cols[i])) return false
                }
                return true
            }

            for (col in 0 until n) {
                if (isLocateQueen(row, col)) {
                    cols[row] = col
                    checkQueen(cols, row + 1)
                }
            }
        }

        checkQueen(IntArray(n), 0)

        return answer
    }
}

 

1. 현재 행 row의 각 열에 대해 퀸을 배치할 수 있는지 확인한다.

  - 이미 배치된 퀸들과 비교하여 같은 열에 있거나 대각선 상에 있는 경우 배치할 수 없으므로 false를 반환한다.

  - 배치할 수 있는 경우 true를 반환한다.

 

2. 만약 배치할 수 있다면, cols 배열에 해당 열을 기록하고 다음 행으로 넘어가 checkQueen 함수를 재귀 호출한다.

---

Comment

대부분의 풀이 방법은 비슷한 것 같다.

모두 백트래킹(Backtracking) 기법을 사용하여 문제를 해결하였다.

백트래킹 자체는 처음 들었으나, 나도 똑같은 방법으로 접근해서 해결하였다.

 

* 백트래킹(Backtracking)은 주어진 문제를 해결하기 위해 가능한 모든 해를 탐색하는 알고리즘 기법 중 하나이다.

* 백트래킹은 재귀적으로 해를 구성해 나가다가 유망하지 않은 해가 나오면, 그 해를 포기하고 이전 상태로 돌아가서 다시 해를 구성해 나가는 방식을 사용한다.