[알고리즘] 그래프 탐색 알고리즘(DFS, BFS)

출처: unsplash.com

 

그래프 탐색이란?

많은 양의 데이터들 중에서 원하는 데이터를 찾는 과정을 탐색이라고 하는데,
그래프에서 원하는 데이터를 찾는 과정을 그래프 탐색이라 부른다.

 

그래프 탐색 알고리즘에는 DFS, BFS가 있다.
DFS(Depth-First Search): 깊이 우선 탐색
BFS(Breadth-First Search): 너비 우선 탐색

 

깊이 우선 탐색(DFS)

깊이 우선 탐색 알고리즘은 그래프의 자식 데이터에 들어간 후, 자식의 자식 데이터를 자식의 자식의 자식 데이터를 들어가는 식으로, 한 가지를 끝까지 파고 들어가서 탐색하는 알고리즘을 뜻한다.

출처: https://jin1ib.tistory.com/entry/BFS-DFS-1

 

한 줄기를 끝까지 파고든 후, 다음 줄기로 이동해 다시 끝까지 파고드는 방식으로 작동하는 알고리즘이다.

 

 

너비 우선 탐색(BFS)

너비 우선 탐색은 시작 데이터에서 자신의 자식 데이터들을 모두 탐색하고 그다음 자식의 자식 데이터들을 모두 확인하는 알고리즘이다.

출처: https://jin1ib.tistory.com/entry/BFS-DFS-1

 

1층부터 시작해 2층의 모든 데이터를 확인하고, 그다음 3층의 모든 데이터를 확인하는 방식으로 데이터를 탐색하는 알고리즘이다.

 

 

그래프 탐색 알고리즘을 구현하기

그래프 탐색 알고리즘을 구현하는 방법은 대체로 다음과 같은 방법을 쓴다.

DFS에는 Stack을,
BFS에는 Queue를 사용한다.

 

스택을 이용한 DFS 구현 방법(이론)

초기에 다음과 같은 그래프가 있을 때,

 

시작점으로 지정할 데이터를 찾아 먼저 Stack에 넣어 준다.

 

다음과 같은 과정을 반복한다.

Stack에서 데이터를 빼낸다.
빼낸 데이터와 연관되어 있는 child 데이터를 그래프에서 찾은 후 스택에 넣어 준다(0의 child 데이터는 1이 된다).
연관 child 데이터가 없거나, 이미 한 번 스택에 들어간 데이터는 스택에 데이터를 넣지 않는다.
그리고 빼낸 데이터를 출력한다.

 

주의할 점은 한 번 스택에 들어간 데이터는 다시 스택에 넣지 않는다는 것이다.

위 3가지의 과정을 순서대로 반복하는 것이 DFS 구현 방법이다.

 

DFS는 재귀 호출을 통해 더 쉽게 그래프를 순회할 수 있다.

 

 

큐를 이용한 BFS 구현(이론)

초기에 다음과 같은 그래프가 있을 때,

 

DFS와 같이 초기에 시작할 데이터를 먼저 큐에 넣고 시작한다.

 

다음과 같은 과정을 반복한다.

큐에서 제일 먼저 들어간 데이터를 빼준다.
빼낸 데이터의 자식 데이터들을 모두 큐에 넣어준다(데이터 2의 자식 데이터는 1, 3, 4이다).
빼낼 자식 데이터가 없거나, 이미 한 번 큐에 들어간 데이터는 큐에 넣지 않는다.
빼낸 데이터를 출력한다.

 

DFS와 똑같이 큐에 한 번 들어간 데이터는 다시 큐에 넣어서는 안 된다.

 

위의 예시는 출발점을 0으로 설정하고 시작했지만, 꼭 0과 같은 끝자락 데이터가 아니어도 된다.
3과 5 같은 중앙의 데이터를 시작점으로 잡아도 DFS와 BFS를 구현할 수 있다.

 

 

 

코드로 구현하기

백준의 1260번을 예로 들어서 코드로 구현해 보겠다.

코드로 구현하기 전에 각 노드 간의 관계를 나타낼 2중 리스트와 각 노드의 방문 여부를 알 수 있는 boolean 리스트를 생성한다.

var visited = booleanArrayOf()
var graph = mutableListOf<MutableList<Int>>()

visited에는 노드의 수만큼 size를 지정해 false 또는 true로 변경해 줄 예정이다.

graph는 바깥 리스트의 size는 각 node의 개수만큼으로 설정한다. 내부의 리스트의 size는 설정하지 않는다.

리스트 데이터를 받으면 다음과 같이 나올 것이다.

[]            // 값 0의 접점은 없음
[2, 3, 4]     // 값 1의 접점은 2, 3, 4
[1, 4]
[1, 4]
[1, 2, 3]

위의 리스트는 graph 데이터의 예시이다. 0번째 줄은 node 0의 관계를, 1번째 줄은 node 1의 관계를 뜻한다.

1번째 줄에 2, 3, 4가 들어 있는데, node 1은 node 2, 3, 4와 관계를 맺고 있다는 뜻이다.

 

DFS는 스택을 이용한 코드와 재귀 코드를 보여주겠다.

먼저 재귀를 이용한 dfs 함수이다.

// 재귀 함수를 통한 dfs 구현
private fun dfsRecursion(start: Int) {
    visited[start] = true
    val data = graph[start]
    print("$start ")

    for (node in data) {
        if (!visited[node]) {
            visited[node] = true
            dfsRecursion(node)
        }
    }
}

시작점으로 설정할 데이터를 파라미터로 받는다(start). start를 기점으로 탐색을 시작한다.

시작점에 해당하는 index의 visited를 true로 바꾼다(한 번 방문했다는 것을 표시).

graph에서 start번째 index를 저장하고 처음에 받는 start를 출력한다.

for문을 돌면서 node에 해당되는 visited가 false일 때만 재귀 호출을 해준다.

 

다음으로는 스택을 이용한 dfs 함수이다.

// 스택을 이용한 dfs 구현
private fun dfs(start: Int) {
    val stack: Stack<Int> = Stack()
    stack.push(start)
    visited[start] = true

    while (stack.isNotEmpty()) {
        val data = stack.pop()
        for (node in graph[data]) {
            if (!visited[node]) {
                stack.push(node)
                visited[node] = true
            }
        }

        print("$data ")
    }
}

처음에 start를 받는 것은 똑같다.

데이터 순회용 stack을 생성하고, stack에 첫 데이터인 start를 넣어주고 visited에 체크를 해준다.

다음으로 stack이 빌 때까지 반복한다.

stack의 데이터를 뽑아와 data 변수를 만들고 graph의 data번째 값과 관계를 맺고 있는 모든 node를 for문으로 체크한다. 

node번째 visited가 false일 때만 stack에 데이터를 추가하고 visited를 true로 변경한다.

for문을 종료하고 사용된 data를 출력한다.

 

 

BFS는 큐를 이용한 코드를 보여 주겠다.

큐를 이용한 bfs 함수이다.

// 큐를 이용한 bfs 구현
private fun bfs(start: Int) {
    val queue: Queue<Int> = LinkedList()
    queue.add(start)
    visited[start] = true
    print("$start ")

    while (queue.isNotEmpty()) {
        val data = queue.poll()
        for (node in graph[data]) {
            if (!visited[node]) {
                queue.add(node)
                visited[node] = true
                print("$node ")
            }
        }
    }
}

스택을 이용한 dfs와 초반은 비슷하다. 스택 대신 큐를 쓴다는 것이 다르다.

큐를 생성하고 시작점을 큐에 넣고 visited에 체크한다. 그리고 start를 출력한다.

큐가 빌 때까지 반복한다.

스택에서 가장 처음 들어간 데이터인 data를 생성하고 graph의 data번째 값을 기준으로 for문으로 반복한다.

node번째 visited가 false이면 큐에 값을 넣고 visited를 체크하고 출력한다.

 

1260번의 전체 코드는 다음과 같다(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue
import java.util.Stack

var visited = booleanArrayOf()
// graph는 각 노드의 관계를 나타냄.
//[]            // 값 0의 접점은 없음
//[2, 3, 4]     // 값 1의 접점은 2, 3, 4
//[1, 4]
//[1, 4]
//[1, 2, 3]
var graph = mutableListOf<MutableList<Int>>()
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, m, start) = readLine().split(" ").map { it.toInt() }

    graph = MutableList(n+1) { mutableListOf() }
    visited = BooleanArray(n+1)
    for (i in 0 until m) {
        val (relation1, relation2) = readLine().split(" ").map { it.toInt() }

        graph[relation1].add(relation2)
        graph[relation2].add(relation1)
    }

    // 데이터를 정렬해주어야 데이터가 올바른 순서대로 출력됨
    graph.map { it.sort() }

    dfsRecursion(start)
    println()

    visited.fill(false)
    bfs(start)
}

// 재귀 함수를 통한 dfs 구현
private fun dfsRecursion(start: Int) {
    visited[start] = true
    val data = graph[start]
    print("$start ")

    for (node in data) {
        if (!visited[node]) {
            visited[node] = true
            dfsRecursion(node)
        }
    }
}

// 스택을 이용한 dfs 구현
private fun dfs(start: Int) {
    val stack: Stack<Int> = Stack()
    stack.push(start)
    visited[start] = true

    while (stack.isNotEmpty()) {
        val data = stack.pop()
        for (node in graph[data]) {
            if (!visited[node]) {
                stack.push(node)
                visited[node] = true
            }
        }

        print("$data ")
    }
}

// 큐를 이용한 bfs 구현
private fun bfs(start: Int) {
    val queue: Queue<Int> = LinkedList()
    queue.add(start)
    visited[start] = true
    print("$start ")

    while (queue.isNotEmpty()) {
        val data = queue.poll()
        for (node in graph[data]) {
            if (!visited[node]) {
                queue.add(node)
                visited[node] = true
                print("$node ")
            }
        }
    }
}

1260번을 풀 때, graph의 내부 리스트를 정렬해 주어야 문제 예제에 알맞게 출력이 된다는 점만 주의하면서 풀면 쉽게 해결할 수 있다.

 

 

정리

그래프 탐색 알고리즘은 코딩 테스트에 자주 나오는 유형의 문제라고 한다.

2가지의 그래프 탐색 알고리즘 중 자신이 편한 것을 구현하면 되지만, 어떤 경우에는 DFS를 써야 하고, 또 어떤 경우에는 BFS를 써야 하는 경우가 있으므로 둘 다 알아 두어야 한다.

알고리즘을 어떻게 써야 하는지 알았으니, 본격적으로 그래프 문제를 풀어볼 생각이다.

 

 

출처

https://jin1ib.tistory.com/entry/BFS-DFS-1

그래프 탐색 알고리즘(Graph Search Algorithm)

https://jason-api.tistory.com/133

백준1260번 DFS 와 BFS 코틀린

https://velog.io/@daehoon12/%EB%B0%B1%EC%A4%80-1260-DFS%EC%99%80-BFS-Kotlin

[백준 1260] DFS와 BFS (Kotlin)