[백준] 11724 (연결 요소의 개수)

#1 알고리즘

#1-1 '연결 요소의 개수'의 의미

어떤 그래프에 탐색 알고리즘을 최소 n번 적용해야 모든 정점을 방문할 수 있다고 치자. 그 때 n의 값이 바로 '연결 요소의 개수'다. 즉, 본 문제는 미방문한 아무 정점을 골라서 탐색 알고리즘을 수행하는 걸 반복하고 그 반복 횟수를 출력하면 되는 문제다.
 

#1-2 사용한 탐색 알고리즘

그래프 - 깊이 우선 탐색 (DFS, Depth-First Search)

깊이 우선 탐색을 사용했다. 방문한 정점을 담는 Set을 외부에서 주입하기 때문에, 너비 우선 탐색에 비해 본 문제에 적용하기에 적합하다.
 

#2 코드 - 코틀린

package org.example.exam11724.ver2

fun main() {
    val nAndM = readln().split(" ")
    val n = nAndM[0].toInt() // 정점의 갯수
    val m = nAndM[1].toInt() // 간선의 갯수

    // 인접배열
    val adjacency = List(n) { ArrayList<Int>() }
    for (i: Int in 0..<m) {
        val tmp = readln().split(" ")
        val start = tmp[0].toInt() - 1
        val end = tmp[1].toInt() - 1
        adjacency[start].add(end)
        adjacency[end].add(start)
    }
    // 방문 기록용 Set
    val discovered = mutableSetOf<Int>()

    // 연결 요소의 갯수 계산
    var submit = 0
    while (discovered.size != n) {
        submit++
        dfs(adjacency, undiscoveredVertex(discovered), discovered)
    }

    // 연결 요소 갯수 출력
    println(submit)
}

fun dfs(adjacency: List<ArrayList<Int>>, vertex: Int, discovered: MutableSet<Int>) {
    discovered.add(vertex)
    for (neighborVertex in adjacency[vertex]) {
        if (neighborVertex !in discovered) {
            dfs(adjacency, neighborVertex, discovered)
        }
    }
}

fun undiscoveredVertex(discovered: MutableSet<Int>): Int {
    var vertex = 0
    while (true) {
        if (vertex !in discovered) {
            return vertex
        }
        vertex++
    }
}

함수 dfs()의 매개변수 listOfAdjacencyArray는 인덱스의 값을 정점으로 전제한다 (참조: 그래프의 표현). 그리고 코틀린에서 배열의 인덱스는 0-based indexing이다. 허나 11724번 문제의 정점은 1-based indexing이다. 따라서 코드 속 변수 start(간선의 출발점) 및 end(간선의 도착점)에 각각 1씩 빼서 인접 배열에 할당했다.