문제
풀이 언어
Kotlin
코드
import java.lang.Integer.min
import java.util.*
import kotlin.math.abs
import kotlin.system.exitProcess
lateinit var board: Array<Array<Int>>
lateinit var visited: Array<Int>
var min_value = Int.MAX_VALUE
var n = 0
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
board = Array(n) { Array(n) { nextInt() } }
visited = Array(n) { 0 }
search(0, 0)
println(min_value)
}
fun search(index: Int, depth: Int) {
if (depth == n / 2) {
calculate()
return
}
for (i in index until n) {
if (visited[i] == 0) {
visited[i] = 1
search(i + 1, depth + 1)
visited[i] = 0
}
}
}
fun calculate() {
var start = 0
var link = 0
for (i in 0 until n - 1) {
for (j in i until n) {
if (visited[i] == 1 && visited[j] == 1) {
start += board[i][j]
start += board[j][i]
} else if (visited[i] == 0 && visited[j] == 0) {
link += board[i][j]
link += board[j][i]
}
}
}
val score = abs(start - link)
if (score == 0) {
println(score)
exitProcess(0)
}
min_value = min(score, min_value)
}
풀이 방법
개인적으로 백트래킹
어떻게 적용할지를 발견하지 못해서 앞서 작성한 골드
문제보다 어려웠다. 우선 2개의 팀 (스타트팀, 링크팀) 으로 나누어야 한다. 방문 지점을 스타트팀
으로 두고 방문하지 않는 지점을 링크팀
으로 두고 문제를 해결했다.
1. 2개의 팀으로 나누므로 depth == n / 2
인 경우에 점수 계산
fun search(index: Int, depth: Int) {
if (depth == n / 2) {
calculate()
return
}
for (i in index until n) {
if (visited[i] == 0) {
visited[i] = 1
search(i + 1, depth + 1)
visited[i] = 0
}
}
}
2. 방문한 지점을 스타트팀으로, 방문하지 않은 지점을 링크팀으로 두고 점수 계산
for (i in 0 until n - 1) {
for (j in i until n) {
if (visited[i] == 1 && visited[j] == 1) {
start += board[i][j]
start += board[j][i]
} else if (visited[i] == 0 && visited[j] == 0) {
link += board[i][j]
link += board[j][i]
}
}
}
val score = abs(start - link)
min_value = min(score, min_value)
3. 점수의 차이가 0이면 최소값이므로 DFS를 진행하지 않고 종료
if (score == 0) {
println(score)
exitProcess(0)
}
결과
'✍️ 코테 준비 > 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 9663 - N Queen (0) | 2022.03.29 |