[BOJ/Kotlin] 1260번 DFS와 BFS : 그래프

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

문제풀이 아이디어

그래프를 어떻게 입력값으로 받을 것인가를 고민해야한다. 그래프는 인접 행렬과 인접 리스트 방식으로 표현할 수 있다. 
-> 나는 Kotlin 의 LinkedHashMap<Int, LikedList> 을 이용해 인접 리스트 형태로 그래프를 표현하였다.

그리고 bfs를 하기위해 queue 를 이용하고, dfs를 하기위해 stack을 활용했다.
dfs는 재귀를 이용하면 훨씬 더 코드가 간결하다. 문제는 stack으로 풀었지만, 재귀를 이용한 방법도 아래 코드에 작성해두었다. 

코드

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val N = input[0].toInt()
    val M = input[1].toInt()
    val start = input[2].toInt()
    val queue: Queue<Int> = LinkedList()
    val stack = Stack<Int>()
    val visit = BooleanArray(N + 1)

    var graph = LinkedHashMap<Int, LinkedList<Int>>()

    for (i in 0..N) {
        graph.set(i, LinkedList())
    }

    for (i in 0 until M) {
        var str = readLine().split(" ")
        graph.get(str[0].toInt())!!.add(str[1].toInt())
        graph.get(str[1].toInt())!!.add(str[0].toInt())
    }

    graph.forEach {
        it.value.sort()
    }

    dfs(stack, visit, graph,start)

    println()
    initVisit(visit)

    dfsRecursion(start,visit,graph)

    println()
    initVisit(visit)

    queue.offer(start)
    visit[start] = true
    bfs(queue, visit, graph)

}

fun bfs(queue: Queue<Int>, visit: BooleanArray, graph: LinkedHashMap<Int, LinkedList<Int>>) {
    while (queue.isNotEmpty()) {
        val cur = queue.peek()
        print("$cur ")
        queue.poll()
        for (i in graph[cur]!!.indices) {
            var vertex = graph[cur]!![i]
            if (visit[vertex]) continue
            queue.offer(vertex)
            visit[vertex] = true
        }
    }
}

fun dfsRecursion(start:Int,visit:BooleanArray,graph: LinkedHashMap<Int, LinkedList<Int>>){
    visit[start] = true
    print("$start ")
    for (i in graph[start]!!.indices) {
        if (visit[graph[start]!![i]]) continue
        dfsRecursion(graph[start]!![i],visit,graph)
    }
}

fun dfs(stack: Stack<Int>, visit: BooleanArray, graph: LinkedHashMap<Int, LinkedList<Int>>,start:Int) {
    stack.push(start)
    while (stack.isNotEmpty()) {
        val cur = stack.peek()
        stack.pop()
        if (visit[cur]) continue
        visit[cur] = true
        print("$cur ")
        for (i in graph[cur]!!.indices) {
            val vertex = graph[cur]!![graph[cur]!!.size - 1 - i]
            if (visit[vertex]) continue
            stack.push(vertex)
        }
    }
}

fun initVisit(visit: BooleanArray) {
    for (i in visit.indices) {
        visit[i] = false
    }
}

배운점

- 그래프의 입력을 인접리스트와 인접 행렬로 표현할 수 있고 인접리스트로 표현할 때 Kotlin의 LinkedHashMap을 이용하면 Key값으로 연결된 vertex들을 바로 파악 할 수 있어 편리한 것 같다. 

- DFS에서는 BFS와 같이 만나는 즉시 방문하지 않고, 가장 깊은 곳 까지 간 다음 끝에서 방문해야함을 깨달았다. 코드를 작성할 때 순서에 유의해야겠다. 

- DFS를 구현하는 방법은 2가지가 있는데, Stack과 재귀 방식이 있다. 코드 간결성 측면에서는 재귀가 훨씬 더 나음을 알 수 있었다. 재귀의 실행 순서를 잘 이해해야겠다.