[백준 15649번] [Kotlin] N과 M (1)

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

15649번: N과 M (1)

 

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

 

 

설명

 

백트래킹 (Back Tracking)

 

백트래킹(Back Tracking)을 연습하기에 아주 좋은 문제입니다.

백트래킹, 우리 말로는 후퇴 탐색 혹은 퇴각 탐색 등으로 번역되는데,

이름에서 느껴지는 뉘앙스와 같이 주어진 해를 찾다가 막다른 길을 발견했을 때, 후퇴하여 다른 길을 찾는 방법입니다.

 

무엇인지 감이 잘 안오시죠?

그래프 탐색 알고리즘중 하나인 DFS를 사용한 백트래킹 예시를 하나 준비해왔습니다.

 

빨간색이 시작 노드, 검정색이 목표 노드라고 했을 때, DFS를 사용해

후퇴 탐색을 하게 된다면 아래 그림처럼 나올 것입니다.

 

 

막다른 해를 만났을 때, 후퇴하여 다른 길을 탐색한다. 라는 말이

정확히 어떤 말인지는 몰라도, 어느정도 감은 오셨죠?

 

'후퇴(back)' - '탐색(tracking)'의 의미를 직관적으로 알기 쉬운 DFS를 예시로 들었지만,

백트래킹이 DFS를 의미하는 것은 아닙니다.

DFS는 백트래킹의 방법 중 하나이며, BFS와 브루트포스 등을 사용한 백트래킹도 가능합니다.

 

DFS, BFS, 브루트포스 중 무엇을 사용해야 하는지는 상황에 따라 다릅니다.

다만, 이 문제 같은 경우 DFS를 사용한 백트래킹이 더 적합해 보이기에, 저는 DFS를 사용해 풀이해보겠습니다.

 

 

소스코드

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) {
    // 길이가 m인 수열을 만들었다면
    if (len == m) {
        println(str)
        return
    }

    for (i in 1..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 // 방문 여부를 다시 미방문 상태로 변경
        }
    }
}

 

중복를 허용하지 않는 수열이기 때문에 방문 여부를 visited로 체크해주었습니다.

그리고, 방문하지 않은 노드들에 대해 숫자를 이어 붙이며 재귀적으로 해당 노드를 탐색합니다.

 

 

후기

백트래킹을 연습하기 좋은 n과 m 시리즈 첫 번째 문제입니다.

n과 m 시리즈는 총 12번까지 있으며,

1번부터 12번까지 모두 풀어보고 나면, 백트래킹에 대해 어느정도 감을 잡으실 수 있을 거라 생각합니다.