[Algorithm/Kotlin] 백준 1260번 DFS와 BFS: 탐색 알고리즘 구현 및 원리

1. 문제 설명

주어진 그래프에서 DFS와 BFS 탐색을 수행한 결과를 출력하는 문제입니다.
방문할 수 있는 정점이 여러 개인 경우, 번호가 작은 정점부터 우선 방문해야 합니다.

입력

• 첫 번째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점 V가 주어집니다.
• 이후 M개의 줄에는 양방향 간선이 연결하는 두 정점의 번호가 주어집니다.

출력

• 첫 번째 줄: DFS 탐색 결과
• 두 번째 줄: BFS 탐색 결과
• 정점 방문 순서대로 출력합니다.

---

2. 문제 해결 아이디어

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

• 스택(Stack) 또는 재귀(Recursion)를 이용해 탐색을 수행합니다.
• 현재 정점에서 가능한 한 깊이 들어가며 방문한 후, 더 이상 갈 곳이 없으면 되돌아옵니다.
• 재귀 함수(Recursive Function) 를 활용하여 구현합니다.

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

• 큐(Queue)를 이용해 탐색을 수행합니다.
• 현재 정점에서 가까운 노드(이웃한 정점)부터 먼저 방문하는 방식입니다.
• 반복문(while)과 큐를 사용하여 구현합니다.

---

3. 구현 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M, V) = br.readLine().split(" ").map { it.toInt() }

    val graph = Array(N + 1) { mutableListOf<Int>() }

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

    // 방문할 수 있는 정점이 여러 개인 경우 번호가 작은 것부터 방문해야 하므로 정렬
    for (i in 1..N) {
        graph[i].sort()
    }

    val visitedDFS = BooleanArray(N + 1)
    dfs(V, graph, visitedDFS)
    println()

    val visitedBFS = BooleanArray(N + 1)
    bfs(V, graph, visitedBFS)
}

// DFS 구현 (재귀)
fun dfs(node: Int, graph: Array<MutableList<Int>>, visited: BooleanArray) {
    visited[node] = true  // 현재 노드를 방문 처리
    print("$node ")

    for (next in graph[node]) {
        if (!visited[next]) {
            dfs(next, graph, visited)  // 방문하지 않은 노드가 있다면 재귀 호출
        }
    }
}

// BFS 구현 (Queue 사용)
fun bfs(start: Int, graph: Array<MutableList<Int>>, visited: BooleanArray) {
    val queue: Queue<Int> = LinkedList()
    queue.add(start)
    visited[start] = true  // 시작 노드를 방문 처리

    while (queue.isNotEmpty()) {
        val current = queue.poll()  // 큐에서 노드 꺼내기
        print("$current ")

        for (next in graph[current]) {
            if (!visited[next]) {
                queue.add(next)  // 방문하지 않은 노드를 큐에 추가
                visited[next] = true  // 방문 처리
            }
        }
    }
}

---

4. DFS & BFS 탐색 과정 상세 설명

예제 입력

4 5 1
1 2
1 3
1 4
2 4
3 4

---

DFS(재귀) - 깊이 우선 탐색 과정

DFS는 재귀 함수를 이용해 구현됩니다.
재귀 호출이 진행되면서 스택(Stack) 구조를 형성하여 깊이 우선 탐색을 수행합니다.

DFS 실행 과정 (V = 1)

1. dfs(1) 호출 → 방문: 1
   •    visited[1] = true
   •    인접 노드 [2, 3, 4] 중 가장 작은 2를 탐색
2. dfs(2) 호출 → 방문: 2
   •    visited[2] = true
   •    인접 노드 [1, 4] 중 방문하지 않은 4를 탐색
3. dfs(4) 호출 → 방문: 4
   •    visited[4] = true
   •    인접 노드 [1, 2, 3] 중 방문하지 않은 3을 탐색
4. dfs(3) 호출 → 방문: 3
   •    visited[3] = true
   •    인접 노드 [1, 4] 모두 방문 완료 → 탐색 종료
   •    dfs(4)로 돌아감 → dfs(2)로 돌아감 → dfs(1)로 돌아감 → 종료

최종 DFS 탐색 결과

1 2 4 3

---

BFS(큐) - 너비 우선 탐색 과정

BFS는 큐(Queue)를 이용하여 구현됩니다.
큐는 FIFO(First In, First Out) 구조를 가지며, 가까운 노드부터 탐색하는 방식입니다.

BFS 실행 과정 (V = 1)

1. 큐에 1 추가 → queue = [1]
2. queue.poll() → 1 → 방문: 1
   •    visited[1] = true
   •    인접 노드 [2, 3, 4] 추가 → queue = [2, 3, 4]
3. queue.poll() → 2 → 방문: 2
   •    visited[2] = true
   •    인접 노드 [1, 4] 중 4는 이미 큐에 존재 → 패스
   •    현재 큐 상태: queue = [3, 4]
4. queue.poll() → 3 → 방문: 3
   •    visited[3] = true
   •    인접 노드 [1, 4] 모두 방문 완료
   •    현재 큐 상태: queue = [4]
5. queue.poll() → 4 → 방문: 4
   •    visited[4] = true
   •    인접 노드 [1, 2, 3] 모두 방문 완료 → 탐색 종료
   •    현재 큐 상태: queue = [] (빈 큐)

최종 BFS 탐색 결과

1 2 3 4

---

5. 정리

• DFS는 재귀(스택) 구조를 활용하여 깊이 우선 탐색을 수행합니다.
• BFS는 큐(Queue) 구조를 활용하여 너비 우선 탐색을 수행합니다.
• DFS는 방문한 노드를 재귀적으로 호출하며, 호출이 끝나면 다시 이전 호출 지점으로 되돌아갑니다.
• BFS는 큐에서 노드를 하나씩 꺼내고(poll()), 아직 방문하지 않은 인접한 노드를 큐에 추가하며 탐색을 진행합니다.
• 번호가 작은 정점부터 방문하기 위해 정렬(sort())을 수행합니다.

---

문제링크: https://www.acmicpc.net/problem/1260