[백준 15650번] [Kotlin] N과 M (2)

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

15650번: N과 M (2)

 

난이도 : 실버 3
태그 : 백트래킹

 

 

설명

N과 M 시리즈. 2번째 문제입니다.

1번과 다른 점은 1번은

1 2 3, 2 1 3, 3 2 1, 3 1 2 모두 가능하였지만,

2번 문제는 오름차순 이므로

1 2 3만 가능하고 2 1 3, 3 2 1, 3 1 2 모두 허용하지 않습니다.

 

1번의 소스를 활용할 수 있을 것 같네요.

 

 

소스코드

lateinit var visited: Array<Boolean>
lateinit var arr: Array<Int>

var n = 0
var m = 0

fun main() {
    val nm = readLine()!!.split(" ")
    m = nm[1].toInt()
    n = nm[0].toInt()

    arr = Array(n + 1) { i -> i }
    visited = Array(n + 1) { false }

    dfs(1, 0, "")
}

fun dfs(idx: Int, len: Int, str: String) {
    if (len == m) {
        println(str)
        return
    }

    for (i in idx..n) {
        if (!visited[i]) {
            visited[i] = true

            if (len == 0)
                dfs(i, 1, arr[i].toString())
            else
                dfs(i, len + 1, "$str ${arr[i]}")

            visited[i] = false
        }
    }
}

 

1번의 소스와 다른 점은 dfs 내 for문의 시작이 idx 부터 라는 점 입니다.

1번은 3번 노드를 탐색하고 1번 노드를 탐색하는 것이 가능했습니다. 중복없이 고르기만 하면 되었으니까요.

하지만 이 문제에서는 3번 노드를 탐색하고 1, 2번 노드를 탐색하면 오름차순 조합을 위반하기 때문에,

항상 마지막으로 탐색한 노드보다 큰 노드를 탐색하여야 합니다.

 

 

후기

n과 m 시리즈는 문제별로 미묘하게 다른 부분에 맞춰 dfs 함수를 수정하는 맛이 있습니다.

미묘한 차이를 캐치하기 위해 머리를 쥐어짜다 보면, 백트래킹에 대한 이해도 역시 깊어집니다.