[Chapter18] - 그래프로 뭐든지 연결하기

[Jwhyee]

그래프와 트리

모든 트리는 그래프지만, 그래프가 트리는 아니다. 그래프는 서로 순환적으로 참조하는 사이클을 형성하는 노드가 있을 수 있지만, 트리에는 사이클이 있을 수 없다.

그래프 탐색

깊이 우선 탐색(DFS)

• 제목 : 텀 프로젝트
• 난이도 : 골드3

private var cnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val t = readLine().toInt()

    repeat(t) {
        val n = readLine().toInt()
        val students = readLine().split(" ").map { it.toInt() - 1 }.toIntArray()

        val visited = BooleanArray(n) { false }
        val finished = BooleanArray(n) { false }

        cnt = 0

        repeat(n) { student ->
            dfs(visited, finished, students, student)
        }

        bw.write("${n - cnt}")
        bw.newLine()
    }

    bw.flush()

    bw.close()
    close()
}

private fun dfs(
    visited: BooleanArray,
    finished: BooleanArray,
    students: IntArray,
    current: Int
) {
    if (visited[current]) return

    visited[current] = true

    val next = students[current]

    if (!visited[next]) {
        dfs(visited, finished, students, next)
    } else {
        if (!finished[next]) {
            cnt++

            var i = next
            while (i != current) {
                cnt++
                i = students[i]
            }
        }
    }

    finished[current] = true
}

데이크스트라

• 제목 : 최단 경로
• 난이도 : 골드4

package bfs  
  
import java.util.*  
  
private const val INF = 100_000_000  
  
fun main() = with(System.`in`.bufferedReader()){  
    val bw = System.out.bufferedWriter()  
  
    var st = StringTokenizer(readLine())  
  
    val (v, e) = st.nextToken().toInt() to st.nextToken().toInt()  
  
    val k = readLine().toInt() - 1  
  
    val graph = Array(v) { arrayListOf<Pair<Int, Int>>() }  
    val distance = IntArray(v) { INF }  
  
    repeat(e) {  
        st = StringTokenizer(readLine())  
        val (u, v, w) = Triple(  
            st.nextToken().toInt() - 1, st.nextToken().toInt() - 1, st.nextToken().toInt()  
        )  
  
        graph[u] += v to w  
    }  
  
    bfs(k, distance, graph)  
  
    repeat(v) { i ->  
        val target = distance[i]  
        val result = if(target == INF) "INF" else "$target"  
  
        bw.write(result)  
        bw.newLine()  
    }  
  
    bw.flush()  
    bw.close()  
    close()  
}  
  
private fun bfs(  
    k: Int,  
    distance: IntArray,  
    graph: Array<ArrayList<Pair<Int, Int>>>,  
) {  
    val queue = PriorityQueue<Pair<Int, Int>> { a, b -> a.second - b.second }  
    val visited = BooleanArray(graph.size) { false }  
  
    queue += k to 0  
    distance[k] = 0  
  
    while (queue.isNotEmpty()) {  
        val (curNode, curWeight) = queue.poll()  
  
        if(visited[curNode]) continue  
  
        visited[curNode] = true  
  
        val nextNodeList = graph[curNode]  
  
        nextNodeList.forEach { (nextNode, weight) ->  
            if (distance[nextNode] > distance[curNode] + weight) {  
                distance[nextNode] = distance[curNode] + weight  
                queue += nextNode to distance[nextNode]  
            }  
        }  
    }  
}