N과 M (1)
문제
풀이 언어
Kotlin
코드
import java.util.*
lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
m = nextInt()
visit = Array(n + 1) { 0 }
input = Array(n + 1) { 0 }
dfs(0)
}
fun dfs(depth: Int) {
if (depth == m) {
for (i in 0 until m) {
print("${input[i]} ")
}
println()
return
}
for (i in 0 until n) {
if (visit[i] == 0) {
visit[i] = 1
input[depth] = i + 1
dfs(depth + 1)
visit[i] = 0
}
}
return
}
풀이 방법
이 문제는 백트래킹
을 활용하는 문제이다. 백트래킹은 완전 탐색 기법 중에 하나로 DFS (Depth First Search)
에서 가능성이 없는 경우의 수는 배제하여(가지치기) 탐색 속도를 향상시키는 방법이다.
우선 입력으로 주어진 n
과 m
에 대해 알아보자. n은 탐색이 진행되는 첫 번째 숫자, m은 탐색 깊이
를 의미한다. 이미 방문한 지점은 Pass
하고 방문하지 않은 지점일 때 더 높은 Depth
에서 탐색을 진행한다. 이 때 m
과 같은 depth 에 진입한 경우 input
에 저장된 결과를 출력한다.
가령 4, 4 가 주어졌다고 가정하면 아래와 같이 탐색을 진행한다.
1
11(pass)
12
122(pass)
123
1233(pass)
1234
...
결과
N과 M (2)
문제
풀이 언어
Kotiln
코드
import java.util.*
lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
m = nextInt()
visit = Array(n + 1) { 0 }
input = Array(n + 1) { 0 }
dfs(0, 0)
}
fun dfs(depth: Int, before : Int) {
if (depth == m) {
for (i in 0 until m) {
print("${input[i]} ")
}
println()
return
}
for (i in 0 until n) {
if (visit[i] == 0 && before < i + 1) {
visit[i] = 1
input[depth] = i + 1
dfs(depth + 1, i + 1)
visit[i] = 0
}
}
return
}
풀이 방법
이전 문제와 동일하지만 한 가지 조건이 추가되었다. 수열이 오름차순
이어야 한다. 이전에 방문한 지점과 현재 방문한 지점을 비교해서 현재 방문한 지점이 더 큰 경우에만 더 높은 Depth
에서 탐색을 진행하도록 한다.
결과
N과 M (3)
문제
풀이 언어
kotlin
코드
import java.util.*
lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0
var stringBuilder = StringBuilder()
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
m = nextInt()
visit = Array(n + 1) { 0 }
input = Array(n + 1) { 0 }
dfs(0)
println(stringBuilder)
}
fun dfs(depth: Int) {
if (depth == m) {
for (i in 0 until m) {
stringBuilder.append(input[i]).append(" ")
}
stringBuilder.append("\n")
return
}
for (i in 0 until n) {
input[depth] = i + 1
dfs(depth + 1)
}
return
}
풀이 방법
이전 두 문제와 다르게 이번엔 중복
을 허용
한다. 경우의 수가 훨씬 커졌다. 그래서 단순히 print
를 사용하면 시간 초과
가 발생한다. 출력에 대한 시간을 줄이고자 StringBuilder
를 사용했다.
결과
N과 M (4)
문제
풀이 언어
Kotlin
코드
import java.util.*
lateinit var visit: Array<Int>
lateinit var input: Array<Int>
var n: Int = 0
var m: Int = 0
var stringBuilder = StringBuilder()
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
m = nextInt()
visit = Array(n + 1) { 0 }
input = Array(n + 1) { 0 }
dfs(0, 0)
println(stringBuilder)
}
fun dfs(depth: Int, before : Int) {
if (depth == m) {
for (i in 0 until m) {
stringBuilder.append(input[i]).append(" ")
}
stringBuilder.append("\n")
return
}
for (i in 0 until n) {
if (before > i + 1) continue
input[depth] = i + 1
dfs(depth + 1, i + 1)
}
return
}
풀이 방법
이번엔 중복
과 오름차순
을 모두 고려해야 하는 문제이다. 역시 StringBuilder
를 사용해서 출력 시간을 줄인다.
결과
'✍️ 코테 준비 > 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 |