DFS와 BFS with 백준 1260번: DFS와 BFS

1260번: DFS와 BFS

문제

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

입력

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

출력

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

 이 그래프는 백준에 있는 예제를 가져온 그래프이다. 위의 그래프를 예로 들어서 각 방법을 구현해 보겠다. 

import java.util.*

var graph = Array(0) { Array(0) { 0 } }
var visited = Array(0) { false }
var sb = StringBuilder()

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m, v) = readLine().split(" ").map { it.toInt() }
    graph = Array(n + 1) { Array(n + 1) { 0 } }

    repeat(m) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        graph[a][b] = 1
        graph[b][a] = 1
    }

    visited = Array(n + 1) { false }

    dfs(n, v)
    sb.append('\n')

    visited = Array(n + 1) { false }
    bfs(n, v)
    print(sb)
}

 일단은 입력받은 정보를 이용해 그래프를 만들어 주었다. 계속해서 각 구현을 해보도록 하겠다.

 

DFS 

---

DFS는 Depth-First Search로 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하는 그래프 탐색 기법이다. 

https://toonraon.tistory.com/44

 이 과정을 코드로 구현하는 방법은 크게 스택을 이용하거나 재귀 함수를 이용하는 방법이 있다. 

 

DFS를 스택으로 구현하는 과정은 다음과 같다.

1. 스택에 시작 노드를 넣는다.
2. 스택의 top을 pop하고 pop되어진 노드의 자식 노드들을 push한다.
3. 이 과정을 반복한다.

DFS는 스택을 구현하는 방법보다 재귀함수를 많이 사용하기에 다음과 같이 구현하였다.

fun dfs(n: Int, v: Int) {
    visited[v] = true
    sb.append("$v ")

    for (i in 1..n) {
        if (graph[v][i] == 1 && !visited[i])
            dfs(n, i)
    }
}

 

BFS

---

BFS는 Breadth-First Search로 시작 정점으로부터 가장 가까운 정점으로 먼저 이동하고 먼 정점을 나중에 방문하는 방법이다.

BFS는 주로 큐로 구현한다.

 

BFS를 큐로 구현하는 과정은 다음과 같다.

1. 큐에 시작 노드를 넣는다
2. 큐의 dequeue를 한 후 dequeue 되어진 노드와 연결되어 있고, 방문하지 않은 노드를 enqueue한다.
3. 큐가 비어있을때까지 반복한다.

fun bfs(n: Int, v: Int) {
    val queue: Queue<Int> = LinkedList<Int>()
    queue.add(v)
    visited[v] = true
    sb.append("$v ")

    while (queue.isNotEmpty()) {
        val top = queue.poll()
        for (i in 1..n) {
            if (graph[top][i] == 1 && !visited[i]) {
                queue.add(i)
                visited[i] = true
                sb.append("$i ")
            }
        }
    }
    queue.clear()
}

 

Reference

[코딩테스트 대비] DFS, BFS 정리

[알고리즘-이론]그래프의 검색 알고리즘 - DFS(Stack)와 BFS(Queue)

코틀린 DFS, BFS 코드

 

[백준] 1260번: DFS와 BFS - kotlin