[백준] 1260번 : DFS와 BFS (Kotlin)

코딩테스트에서 가장 출제율이 높다는 DFS와 BFS를 백준 대표 예제를 통해 공부해 보겠습니다.

 

1260번: DFS와 BFS

import java.util.*

fun main() {
    val (n,m,v) = readLine()!!.split(" ").map {it.toInt()}
    val graph = Array(n+1) {IntArray(n+1)}
    var visit = ArrayList<Int>()

    repeat(m) {
        val (x,y) = readLine()!!.split(" ").map {it.toInt()}

        graph[x][y] = 1
        graph[y][x] = 1
    }

    dfs(v, graph, visit)  // dfs 탐색
    println()

    visit = ArrayList<Int>()  // 방문 정점 초기화
    bfs(v, graph, visit)  // bfs 탐색

}

fun dfs(start: Int, graph: Array<IntArray>, visit: ArrayList<Int>) {
    visit.add(start)
    print("$start ")

    for (i in 1 until graph.size) {
        if (graph[start][i] == 1&& !visit.contains(i)) {
            dfs(i,graph,visit)
        }
    }
}

fun bfs(start: Int, graph: Array<IntArray>, visit: ArrayList<Int>) {
    val queue = LinkedList<Int>()
    queue.add(start)
    visit.add(start)

    while(queue.isNotEmpty()) {
        val x = queue.poll()
        print("$x ")

        for (i in 1 until graph.size) {
            if (graph[x][i] == 1 && !visit.contains(i)) {
                queue.add(i)
                visit.add(i)
            }
        }
    }
}

DFS는 깊이우선탐색으로 재귀를 통해, BFS는 너비우선탐색으로 큐(LinkedList)를 이용합니다.

 

먼저, 정점이 연결된 경우는 해당 정점에 해당하는 graph의 값을 1로 변경합니다. 방향이 없는 간선이기 때문에 양방향으로 graph의 인덱스 값을 1로 변경합니다.

 

탐색 시작 정점인 v가 주어지기 때문에 DFS는 v에서 시작해 연결된 정점이 있는 경우 더 이상 연결된 정점이 없을 때까지 재귀함수를 호출해 가면서 깊이 우선으로 탐색합니다.

BFS도 마찬가지로 v에서 시작하지만 시작 정점으로부터 해당 정점에 연결된 정점들을 모두 탐색한 후 다음 깊이의 정점을 탐색합니다.