SW Test/Programmers
[Programmers] Lv2. N-Queen(kotlin)
An effort will never betray π
2022. 7. 26. 19:08
λ°μν
λ¬Έμ
μμ
νμ΄
- N-Queenμ λ°±νΈλνΉμ λνμ μΈ λ¬Έμ λ‘ yμΆμ νλμ© λ΄λ €κ°λ©΄μ xμΆμ νλ² μννμ¬ Queenμ΄ λμμ§ μ μλ κ³³μ μ°Ύλ λ¬Έμ μ λλ€.
- νλμ© νμνλ©΄μ μ°Ύμλ λμ§λ§ μνμ μΌλ‘ μ’νλ₯Ό νμ©νμ¬ λ¬Έμ λ₯Ό νλ©΄ λΉ λ₯΄κ² ν μ μμ΅λλ€.
- λκ°μ λΌλ¦¬λ κ°μ λΌμΈμ Queenμ΄ μμΌλ©΄ μλλλ° μ’νμ κΈ°μΈκΈ°λ κ·μΉμ ν΅ν΄μ κ°μ λκ°μ μΈμ§ μλμ§ μ μ μμ΅λλ€.
- μ€λ₯Έμͺ½ μλλ‘ ν₯νλ λκ°μ μμ y-x κ°μ΄ λμΌν μ’νλ κ°μ λκ°μ μμ μ‘΄μ¬ν©λλ€.
- λ§μ°¬κ°μ§λ‘ μΌμͺ½ μλλ‘ ν₯νλ λκ°μ λΌλ¦¬λ y+x κ°μ΄ λμΌν©λλ€.
- λ°λΌμ yμ’νλ νλμ© λ΄λ €κ°λ©΄μ xμ’νλ§ 0λΆν° n-1κΉμ§ μννμ¬ dlist (down list), rdlist(right down list) , ldlist(left down list) μ μΆκ°νκ³ μ΄λ―Έ μ’νκ°μ΄ ν¬ν¨λμ΄ μμΌλ©΄ 건λλ°λ©΄ λ©λλ€.
class Solution {
var answer = 0
fun backtraking(n: Int, y: Int, dlist: List<Int>, rdlist: List<Int>, ldlist: List<Int>){
if(n == y){
answer++
return
}
(0 until n).forEach{ i ->
if(dlist.contains(i).not() && rdlist.contains(y-i).not() && ldlist.contains(y+i).not()){
backtraking(n, y+1, dlist + listOf(i), rdlist + listOf(y -i), ldlist + listOf(y + i))
}
}
}
fun solution(n: Int): Int {
backtraking(n,0,listOf<Int>(), listOf<Int>(), listOf<Int>())
return answer
}
}
μ°Έκ³
- ν¨μν νλ‘κ·Έλλ° μΈμ΄μΈ kotlinμ νΉμ±μ λ§κ² ν¨μλ₯Ό λ§μ΄ μ΅νμ π½
- https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-list/contains.html
λ°μν