Kotiln 연습하기(9) - DFS / BFS

김검정 2025. 4. 11. 10:33

2025. 4. 11. 10:33

그래프(Graph)란 무엇일까?

그래프는 정점(Vertex)와 간선(Edge)으로 구성된 자료구조이다.

정점(Vertex) : 그래프의 구성요소로, 사람이나 도시처럼 개별 요소를 나타낸다.
간선(Edge) : 정점들을 연결하는 선이다. 두 정점 사이의 관계(예:도로, 친구 관계)를 나타낸다.
예시 : 학교에서 여러 학생(정점)들이 친구 관계(관선)를 맺고 있는 것을 그래프로 생각할 수 있다.

그래프의 표현 방법

그래프를 컴퓨터에서 표현하는 방법에는 여러 가지가 있다. 가장 일반적인 두 가지 방법은 인접 리스트와 인접 행렬이다.

인접 리스트(Adjacency List) : 각 정점에 연결된 정접들의 리스트를 저장한다.

예시

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]

인접 행렬(Adjacency Matrix) : 정점 간의 연결 여부를 2차원 배열 형태로 저장한다.

예시

matrix[0][1] = 1

현실 세계에서의 그래프 예시로는

학교 네트워크 : 학생들을 정점으로 하고, 친구 관계를 간선으로 표현
지도와 도로 : 도시를 정점, 도로를 간선으로 표현하여 경로 탐색 문제 해결
인터넷 : 웹 페이지를 정점으로 하고, 하이퍼링크를 간선으로 표현하여 검색 알고리즘 등에 응용

등이 있다.

깊이 우선 탐색(DFS, Depth First Search)

1. DFS 의 기본 원리

DFS는 시작 정점에서 출발하여 한 방향으로 끝까지 탐색한 후, 더 이상 진행할 수 없으면 마지막 분기점으로 돌아가 다른 경로를 탐색하는 방식이다. 이러한 과정은 재귀 호출을 통해 자연스럽게 구현된다.

2. DFS의 동작 방식과 재귀 호출

동작 방식 :

시작 정점을 방문하고, 방문 목록에 추가한다.
현재 정점에서 인접한 정점 중 아직 방문하지 않은 정점을 선택한다.
선택한 정점으로 이동하여 같은 과정을 반복한다.
더 이상 방문할 정점이 없으면, 이전 정점으로 되돌아가 (Backtracking) 다른 경로를 탐색한다.

재귀 호출 : DFS는 재귀적으로 자신을 호출하면서, 깊은 경로를 먼저 탐색한다.

3. DFS의 장단점

장점 :

구현이 간단하고 직관적이다.
경로 탐색, 사이클 검출 등 다양한 문제에 응용할 수 있다.

단점 :

재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.
최악의 경우 모든 정점을 방문하므로, 시간 복잡도가 높을 수 있다.

4. DFS 구현 예제(Kotlin)

// DFS를 구현하기 위해, 방문한 정점을 기록할 집합과 재귀 함수를 사용합니다.
fun dfs(node: Int, visited: MutableSet<Int>, graph: Map<Int, List<Int>>) {
    // 현재 정점을 방문 목록에 추가하고, 출력합니다.
    visited.add(node)
    println("DFS 방문: $node")

    // 현재 정점과 연결된 모든 정점을 순회합니다.
    for (neighbor in graph[node] ?: emptyList()) {
        // 아직 방문하지 않은 정점이면 재귀 호출합니다.
        if (!visited.contains(neighbor)) {
            dfs(neighbor, visited, graph)
        }
    }
}

fun mainDFS() {
    // 간단한 무방향 그래프를 인접 리스트로 표현합니다.
    val graph: Map<Int, List<Int>> = mapOf(
        0 to listOf(1, 2), // 0번 정점은 1번,2번 정점에 간선을 갖는다.
        1 to listOf(0, 3),
        2 to listOf(0, 3),
        3 to listOf(1, 2)
    )
    
    val visited = mutableSetOf<Int>()
    println("=== DFS 탐색 결과 ===")
    dfs(0, visited, graph)
}

위에 코드에서 인접 리스트로 표현된 그래프를 실제로 살펴보면

위 그림에서 방향성을 나타내는 화살표를 빼고 안쪽에 있는 간선 3개를 빼면 위의 코드의 그래프이다.

해당 코드를 실행해보면 시작 정점 0에서 시작하여 0 > 1 > 3> 2 순으로 방문을 진행하고, 각 단계에서 재귀 호출이 이루어지고, 되돌아가며 다른 경로를 탐색하는 모습은 미로에서 한 길로 쭉 들어갔따가 다시 돌아가는 것과 비슷하다.

너비 우선 탐색(BFS, Breadth First Search)

1. BFS의 기본 원리

BFS는 시작 정점에서부터 인접한 모든 정점을 먼저 방문하고, 그 다음 단계의 정점을 방문하는 방식이다. 즉, "가까운 것부터 넓게" 탐색하는 방법이다.

2. BFS의 동작 방식과 큐의 역할

동작 방식 :

시작 정점을 방문하고, 큐에 추가한다.
큐에서 정점을 꺼내 그 정점과 인접한 모든 정점을 방문한다.
방문한 정점을 큐에 추가하면서, 순차적으로 탐색한다.

큐의 역할 : BFS에서는 먼저 들어온 정점을 먼저 처리하는 FIFO(선입선출) 자료구조인 큐를 사용한다.

3. BFS의 장단점

장점 :

최단 경로를 찾는 데 효과적이다.
큐를 사용하므로 DFS보다 스택 오버플로우 위험이 적다.

단점 :

모든 인접 정점을 저장해야 하므로 메모리 사용량이 많아질 수 있다.
그래프의 모든 정점을 한 번씩 방문하므로, 큰 그래프에서는 시간이 오래 걸릴 수 있다.

4. BFS 구현 예제(Kotlin)

import java.util.LinkedList
import java.util.Queue

fun bfs(start: Int, graph: Map<Int, List<Int>>) {
    val visited = mutableSetOf<Int>()
    val queue: Queue<Int> = LinkedList()

    // 시작 정점을 방문 처리하고 큐에 추가합니다.
    visited.add(start)
    queue.offer(start)

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        println("BFS 방문: $node")
        
        // 현재 정점과 연결된 모든 정점을 순회하며 방문하지 않은 정점을 큐에 추가합니다.
        for (neighbor in graph[node] ?: emptyList()) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor)
                queue.offer(neighbor)
            }
        }
    }
}

fun mainBFS() {
    // 간단한 무방향 그래프를 인접 리스트로 표현합니다.
    val graph: Map<Int, List<Int>> = mapOf(
        0 to listOf(1, 2),
        1 to listOf(0, 3),
        2 to listOf(0, 3),
        3 to listOf(1, 2)
    )

    println("=== BFS 탐색 결과 ===")
    bfs(0, graph)
}

코드의 실행에 대해서 생각해보면 시작 정점 0에서 시작하여, 먼저 0에 인접한 1과 2를 방문하고, 그 후 1과 2의 인접 정점(3 등)을 방문하는 순서로 진행된다.

DFS와 BFS의 비교

1. 탐색 방식의 차이

DFS : 한 방향으로 깊게 들어간 후, 더 이상 진행할 수 없으면 되돌아가는 방식 -> "깊이 우선"으로 탐색한다.
BFS : 시작 정점에서 가까운 정점을 모두 방문한 후, 그 다음 레벨로 넘어가는 방식 -> "너비 우선"으로 탐색한다.

2. 시간 복잡도와 메모리 사용 비교

시간 복잡도 : 두 알고리즘 모두 그래프의 정점 수(V)와 간선 수 (E)에 따라 O(V+E)의 시간 복잡도를 가진다.
메모리 사용 : DFS는 재귀 호출(또는 스택)을 사용하므로 깊이에 따라 메모리 사용량이 결정된다. / BFS는 큐에 모든 인접 정점을 저장하므로, 그래프가 넓을 경우 메모리 사용량이 증가할 수 있다.

언제 각각 사용해야 할까?

DFS 사용 경우 : 경로 깊이가 중요한 경우 / 모든 경로를 탐색해야 하는 문제(예: 순열, 조합, 백트래킹 문제)
BFS 사용 경우 : 최단 경로 문제 / 너비 우선 탐색을 통해 빠르게 탐색할 수 있는 경우

위의 DFS와 BFS는 문제를 더 풀어보면서 Kotlin 을 연습해봐야겠다.

'자료구조&알고리즘 > Kotlin 활용' 카테고리의 다른 글

프로그래머스 (기초) - 5명씩 (0)	2025.04.18
Kotlin 연습하기(10) - 그리디 알고리즘 (2)	2025.04.14
Kotlin 연습하기(7) - 동적 계획(DP) (0)	2025.04.07
Kotlin 연습하기(6) - 선형/이진 검색 (0)	2025.04.04
Kotlin 연습하기(5) - 버블정렬 (0)	2025.04.02

공부