<프로그래머스> N-Queen(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/N-Queen

[프로그래머스]

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

제출 결과

 

설날 연휴를 다 보내고 푸는 첫번째 문제

경우의 수를 따지는 문제라서 약간 포기할까라는 마음이 초반에 들었었지만 억누르고 계속 도전하다보니 뚫렸다.

푸는 방식은 숫자도 그리 크지 않고 한줄 한줄 체크하면 될 거 같아서 DFS를 사용했다.

먼저 첫번째 줄이 정해지면 나머지는 또 경우의 수에 맞춰서 진행하면 되기 때문에 첫번째 줄을 순회하며 재귀함수를 돌렸다.

들어가면 공격범위를 모두 체크하고 공격범위에 들어가지 않는 다음 줄의 칸에 퀸을 배치하고 다음 스텝으로 갔다.

다시 돌아올 때는 현재 퀸의 공격 범위를 다 지워줬다.

이걸 구현하기 위해 현재 줄의 숫자에 -1을 곱해서 공격범위칸을 채웠다.

지울 때는 그 숫자만 지우도록 했다.

공격범위의 대각선처리를 좀 깔끔하게 하고 싶었는데 생각이 나지 않아 좀 길어졌다...

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    private val chessBoard = Array(13) { Array(13) { 0 } }
    private var result = 0
    fun solution(n: Int): Int {

        for (i in 0 until n) {
            checkPosition(Pair(0, i), n)
            removeAttackRange(Pair(0, i), n)
        }

        return result
    }

    private fun checkPosition(position: Pair<Int, Int>, size: Int) {
        addAttackRange(position, size)

        if (position.first == size) {
            result++
            return
        }

        for (i in 0 until size) {
            if (chessBoard[position.first + 1][i] == 0) {
                checkPosition(Pair(position.first + 1, i), size)
                removeAttackRange(Pair(position.first + 1, i), size)
            }
        }
    }

    private fun addAttackRange(position: Pair<Int, Int>, size: Int) {
        chessBoard[position.first][position.second] = 1

        for (i in 0 until size) {
            if (chessBoard[position.first][i] == 0) chessBoard[position.first][i] =
                -(position.first + 1)
            if (chessBoard[i][position.second] == 0) chessBoard[i][position.second] =
                -(position.first + 1)
        }

        var row = 1
        var col = 1
        while (position.first + row < size && position.second + col < size) {
            if (chessBoard[position.first + row][position.second + col] == 0) chessBoard[position.first + row][position.second + col] =
                -(position.first + 1)

            row++
            col++
        }

        row = 1
        col = 1
        while (position.first - row >= 0 && position.second - col >= 0) {
            if (chessBoard[position.first - row][position.second - col] == 0) chessBoard[position.first - row][position.second - col] =
                -(position.first + 1)

            row++
            col++
        }

        row = 1
        col = 1
        while (position.first + row < size && position.second - col >= 0) {
            if (chessBoard[position.first + row][position.second - col] == 0) chessBoard[position.first + row][position.second - col] =
                -(position.first + 1)

            row++
            col++
        }

        row = 1
        col = 1
        while (position.first - row >= 0 && position.second + col < size) {
            if (chessBoard[position.first - row][position.second + col] == 0) chessBoard[position.first - row][position.second + col] =
                -(position.first + 1)

            row++
            col++
        }
    }

    private fun removeAttackRange(position: Pair<Int, Int>, size: Int) {
        chessBoard[position.first][position.second] = 0
        for (i in 0 until size) {
            for (j in 0 until size) {
                if (chessBoard[i][j] == -(position.first + 1)) chessBoard[i][j] = 0
            }
        }
    }
}