문제
풀이 언어
Kotlin
코드
import java.util.*
import kotlin.math.abs
lateinit var array: Array<Int>
var n = 0
var cnt = 0
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
array = Array(n) { 0 }
nQueen(0)
println(cnt)
}
fun nQueen(depth: Int) { // depth는 row
if (depth == n) {
println(depth)
cnt++
return
}
for (i in 0 until n) { // i는 col
array[depth] = i
if (check(depth)) {
nQueen(depth + 1)
}
}
}
fun check(row: Int): Boolean {
for (i in 0 until row) {
// 1. 이전 열 (저장되어 있는 값) 과 비교, index 값이 row 이므로 행은 무조건 다름
if (array[row] == array[i]) return false
// 2. 대각선 비교
else if (abs(array[row] - array[i]) == abs(row - i)) return false
}
return true
}
풀이 방법
우선 N-Queen
문제에 대해 알아보자.
체스에서 Queen
은 상, 하, 좌, 우, 대각선으로 나아갈 수 있다. 이러한 Queen 을 서로 겹치지 않게 체스판 위에 배치하는 문제가 N-Queen
문제이다. Quuen 을 겹치지 않게 배치하기 위해서는 아래 조건을 만족해야 한다.
- 하나의 Queen 의 상, 하, 좌, 우 에는 다른 Queen 이 존재하지 않는다.
- 하나의 Queen 의 대각선에는 다른 Queen 이 존재하지 않는다.
언뜻 보면 2차원 배열로 문제를 해결해야할 것 같지만, 1차원 배열로도 해결이 가능하다. 1차원 배열의 index
를 Row
로, 해당 원소를 Col
으로 사용하면 2차원 배열을 1차원 배열로 표현할 수 있게 된다.
1. 우선 첫번째 행 (체스판의 맨 위) 부터 시작한다.
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
array = Array(n) { 0 }
nQueen(0)
println(cnt)
}
2. array[0] = 0, 즉 (row = 0, col = 0) 에 Queen 을 배치한다.
fun nQueen(depth: Int) { // depth는 row
if (depth == n) {
cnt++
return
}
for (i in 0 until n) { // i는 col
array[depth] = i
if (check(depth)) {
nQueen(depth + 1)
}
}
}
3. 이 때, 해당 위치를 검증한다. 상, 하, 좌, 우, 대각선을 판단하는데 대각선을 검증할 때 abs
를 활용하면 좀 효율적으로 계산할 수 있다. abs(array[row] - array[i])
는 두 Queen 간의 col
차이를 의미하고, abs(row - i)
는 두 Queen 간의 row
차이를 의미한다. 이 값이 같으면 서로 대각선 상으로 존재하는 것이므로 종료한다.
fun check(row: Int): Boolean {
for (i in 0 until row) {
// 1. 이전 열 (저장되어 있는 값) 과 비교, index 값이 row 이므로 행은 무조건 다름
if (array[row] == array[i]) return false
// 2. 대각선 비교
else if (abs(array[row] - array[i]) == abs(row - i)) return false
}
return true
}
결과
참고 자료
'✍️ 코테 준비 > Back Tracking' 카테고리의 다른 글
[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기 (0) | 2022.04.10 |
---|---|
[백트래킹 / Kotlin] BOJ 1987 - 알파벳 (0) | 2022.04.10 |
[백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기 (0) | 2022.03.31 |
[백트래킹 / Kotlin] BOJ 2580 - 스도쿠 (0) | 2022.03.30 |
[백트래킹 / Kotlin] BOJ 15649 ~ 15652 - N과 M (1 ~ 4) (0) | 2022.03.28 |