백준 9663번 N-Queen Kotlin 구현해보기

---

```

백준 9663번 N-Queen Kotlin 구현해 보기

```

Kimc Kotlin Study

이번 글을 통해 배워갈 내용

1. 백준 9663번 N-Queen Kotlin 풀이

---

https://www.acmicpc.net/problem/9663

9663번: N-Queen

백준 9663번 N-Queen는

 

난이도 골드 등급의 문제로서

 

N X N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없게 두는 경우

놓는 방법의 경우의 수를 구하는 코드를 작성하면 됩니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

getInput에서

입력을 받고

 

findNumberOfWaysToPlaceQueen에서

구할 수 있는 모든 경우의 수를 모두 구해줍니다.

 

Brutefoce로 구현하였습니다.

 

import kotlin.math.abs

fun main(args: Array<String>) {
    // input
    val inputDto = getInput()
    // output
    print(solution(inputDto))
}

data class InputDto(
    val queenCnt: Int,
    var count: Int = 0,
    val board: Array<Int>
) {
    private fun isHorizontal(colIdx: Int, i: Int) = board[colIdx] === board[i]
    private fun isDiagonal(colIdx: Int, i: Int) = colIdx - i == abs(board[colIdx] - board[i])
    private fun isPossibleToPlaceQueen(colIdx: Int): Boolean {
        for (i in 0 until colIdx) {
            if (isHorizontal(colIdx, i) || isDiagonal(colIdx, i)) {
                return false
            }
        }
        return true
    }

    fun findNumberOfWaysToPlaceQueen(rowIdx: Int) {
        if (rowIdx == queenCnt) {
            count++
            return
        }
        for (colIdx in 0 until queenCnt) {
            board[rowIdx] = colIdx
            if (isPossibleToPlaceQueen(rowIdx)) {
                findNumberOfWaysToPlaceQueen(rowIdx + 1)
            }
        }
    }
}

fun getInput(): InputDto {
    val queenCnt = readln().toInt()
    val board: Array<Int> = Array(queenCnt) { 0 }
    return InputDto(queenCnt = queenCnt, board = board)
}


fun solution(dto: InputDto): String {
    dto.findNumberOfWaysToPlaceQueen(0)
    return "${dto.count}"
}


// https://codemasterkimc.tistory.com/

 

테스트

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

internal class MainKtTest {

    @Test
    fun test() {
        assertEquals(
            "2",
            solution(
                InputDto(4, 0, Array(4) { 0 })
            )
        )
        assertEquals(
            "92",
            solution(
                InputDto(8, 0, Array(8) { 0 })
            )
        )
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---