[백준 24479번] [Kotlin] 알고리즘 수업 - 깊이 우선 탐색 1

 

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

난이도 : 실버 2
태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색

 

 

설명

이름 처럼 깊이 우선 탐색 (DFS, Depth First Search)의 연습문제 입니다.

그래프를 탐색하는데는 여러 방법이 있습니다.

그 중 꽤 유명한 탐색방법인 DFS를 연습해봅시다.

 

DFS는 트리 or 그래프에서 최대한 깊이 탐색한 후,

더 이상 탐색할 노드가 없을 경우 (막다른 길을 만났을 경우) 뒤로 돌아가,

가장 최근의 갈림길로 돌아가 다른 루트를 탐색합니다.

 

즉, 한 경로를 완전히 탐색했을 때만 다른 경로를 탐색합니다.

이는 미로를 빠져나갈 때 오른쪽 혹은 왼쪽 벽에 손을 대고 쭉 이동하면 결국 출구를 찾는다는 것과 비슷한 원리입니다.

 

이러한 dfs를 구현하는 데에는 스택 혹은 재귀적인 방법이 사용될 수 있습니다만,

보통 재귀가 더 많이 쓰이는 편 입니다.

저 역시 재귀가 깔끔해보여 재귀적으로 구현을 하는 편이고요.

 

 

 

소스코드

import java.util.StringTokenizer

lateinit var connected: Array<ArrayList<Int>>
lateinit var visited: Array<Int>
val sb = StringBuilder()
var cnt = 1

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m, r) = readLine().split(" ").map { it.toInt() }

    connected = Array(n + 1) { ArrayList() }
    visited = Array(n + 1) { 0 }

    repeat(m) {
        val st = StringTokenizer(readLine())
        val (v1, v2) = Array(2) { st.nextToken().toInt() }
        connected[v1].add(v2)
        connected[v2].add(v1)
    }

    connected.forEach { it.sort() }

    dfs(r)

    for (i in 1..n) {
        sb.append(visited[i]).append("\n")
    }
    
    print(sb)
}

fun dfs(idx: Int) {
    if (visited[idx] != 0) return

    visited[idx] = cnt++

    connected[idx].forEach { next ->
        dfs(next)
    }
}

 

 

dfs는 메인 함수에서 시작 노드를 매개 변수로써 넘겨주며 시작합니다.

dfs 함수 내에서는 연결된 노드를 다시 매개 변수로 넘겨주며 자기 자신(dfs)를 호출합니다.

그렇게 넘겨준 매개 변수 노드와 연결된 노드를 또 다시 탐색하고,

그렇게 넘겨준 매개 변수 노드와 연결된 노드를 또 다시 탐색하고

.

.

.

위 과정을 계속 반복하며 dfs가 진행됩니다.

연결된 노드가 없다면/모든 노드를 탐색했다면, 더 이상 dfs를 호출하지 않으므로 자연스레 왔던 길을 되돌아갑니다.

 

 

 

후기

dfs는 bfs와 함께 매우 자주 나오는 유형이죠.

처음에는 재귀 자체가 낮설어 꺼려졌으나,

지금은 너무 재밌습니다.

너무 짜릿해요.

dfs 최고.