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

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

 

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

 

 

설명

알고리즘 수업 - 깊이 우선 탐색 1과 비슷한 문제입니다.

https://uknowblog.tistory.com/323

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

 

다만 다른 점이라면, 탐색 순서라 볼 수 있는데, 인접 정점을 내림차순 순서로 방문한다는 것이 특징입니다,

인접 정점을 내림차순 순서로 방문하는 방법은 간단합니다.

바로 인접 리스트 내 노드 정보를 내림차순(Descending)으로 정렬 후 탐색하면 됩니다.

 

 

 

소스코드

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.sortDescending() }

    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)
    }
}

 

sortDescending()으로 인접 리스트의 연결 정보를 내림차순으로 정렬 후 탐색하였습니다.