코틀린 코딩테스트 강좌, 너비 우선 탐색

1. 문제 설명

이번 문제는 주어진 그래프에서 두 노드 사이의 최단 경로를 찾는 것입니다. 그래프는 인접 리스트 형태로 주어지며, 노드의 개수와 각 노드에 연결된 노드 정보가 제공됩니다. 여러분의 목표는 특정 시작 노드에서 특정 목표 노드까지의 최단 경로를 출력하는 것입니다.

문제


입력:
- 첫 번째 줄: 정점의 개수 N (1 ≤ N ≤ 1000)
- 두 번째 줄: 간선의 개수 M (0 ≤ M ≤ 10000)
- 다음 M개의 줄: 간선 정보 (A B) - A와 B는 각각 연결된 두 노드를 나타냄

- 이어서 마지막 줄에, 시작 노드 S와 목표 노드 T가 주어짐.

출력:
- S에서 T까지 가는 경로의 노드 목록을 출력하시오. 만약 경로가 없다면 "PATH NOT FOUND!"를 출력하세요.

2. 문제 접근 방식

이 문제는 전형적인 BFS 알고리즘을 사용하여 해결할 수 있습니다. BFS는 너비 우선 탐색 방법으로, 시작 노드에서 가까운 노드부터 탐색해 나아가는 방식입니다. 이를 통해 최단 경로를 찾는 것이 가능합니다. BFS 알고리즘의 주요 특징은 다음과 같습니다:

모든 노드를 동일한 깊이로 탐색하므로, 최단 경로를 보장합니다.
큐(Queue)를 사용하여 구현하며, 이론적으로 O(V + E)의 시간 복잡도를 가집니다. 여기서 V는 노드의 개수, E는 간선의 개수입니다.

BFS 알고리즘 단계

초기화: 시작 노드에 대한 방문 표시 및 거리 초기화. 큐에 시작 노드를 삽입.
탐색 과정: 큐가 비어 있지 않은 동안 반복. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드들 중 방문하지 않은 노드를 큐에 추가.
경로 추적: 각 노드의 부모 노드를 기록해 놓아 나중에 경로를 추적할 수 있도록 함.

3. 코틀린 코드 구현

이제 위의 접근 방식에 따라 코틀린으로 BFS를 구현해 보겠습니다. 아래 코드를 참조하여 주어진 문제를 해결하는 방법을 확인하세요.


import java.util.*

data class Edge(val to: Int, val weight: Int)

fun bfs(graph: List>, start: Int, target: Int): List? {
    val queue: Queue = LinkedList()
    val visited = BooleanArray(graph.size)
    val parent = IntArray(graph.size) { -1 }  // 부모 노드 추적
    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val current = queue.poll()

        // 목표 노드를 찾으면 경로 추적
        if (current == target) {
            return tracePath(parent, start, target)
        }

        for (edge in graph[current]) {
            if (!visited[edge.to]) {
                visited[edge.to] = true
                parent[edge.to] = current // 부모 노드 설정
                queue.add(edge.to)
            }
        }
    }
    return null // 경로가 없을 경우
}

fun tracePath(parent: IntArray, start: Int, target: Int): List {
    val path = mutableListOf()
    var current = target

    while (current != start) {
        path.add(current)
        current = parent[current]
    }
    path.add(start)
    path.reverse()  // 역순으로 추가되어 있으므로 반전
    return path
}

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val m = scanner.nextInt()
    val graph = List(n) { mutableListOf() }

    // 그래프 생성
    for (i in 0 until m) {
        val a = scanner.nextInt() - 1
        val b = scanner.nextInt() - 1
        graph[a].add(Edge(b, 1)) // 방향이 없는 그래프이므로 양쪽 다 추가
        graph[b].add(Edge(a, 1))
    }

    val start = scanner.nextInt() - 1
    val target = scanner.nextInt() - 1
    val result = bfs(graph, start, target)

    if (result != null) {
        println(result.joinToString(" "))
    } else {
        println("PATH NOT FOUND!")
    }
}

4. 예시 입출력

예시 1

예시 2


입력:
5 3
1 2
2 3
4 5
1 4

출력:
PATH NOT FOUND!

5. 마무리

이번 강좌에서는 너비 우선 탐색(BFS)을 활용하여 그래프에서 두 노드 사이의 최단 경로를 찾는 문제를 다뤘습니다. BFS는 탐색의 용이함 덕분에 많은 알고리즘 문제에서 유용하게 사용됩니다. 실제 시험이나 코딩테스트에서 BFS를 적절히 활용하여 문제를 해결하는 능력을 기르는 것이 중요합니다.

이제 여러분도 BFS을 활용해 다양한 문제를 풀어보시길 바랍니다. 코틀린으로 구현해 보며 알고리즘의 이해도를 높이고, 현업에서도 사용할 수 있는 능력을 키워보세요!

관련