코틀린 코딩테스트 강좌, DFS와 BFS 프로그램

소개

코딩테스트를 준비하면서 다양한 알고리즘을 배우는 것은 매우 중요합니다. 그 중에서도
DFS(Depth-First Search)와 BFS(Breadth-First Search) 알고리즘은 많은 문제를 해결하는 데 효과적입니다.
이 글에서는 DFS와 BFS의 개념을 이해하고, 이를 활용한 예제를 통해 실제 코딩테스트에 대비하는 방법을 배워보도록 하겠습니다.

DFS와 BFS의 개념

DFS와 BFS는 그래프 탐색을 위한 알고리즘으로, 두 알고리즘의 접근 방식은 각각 다릅니다.

DFS (Depth-First Search)

DFS는 깊이 우선 탐색으로, 한 노드에서 가능한 깊이까지 탐색한 후, 더 이상 탐색할 수 없게 되면
이전 노드로 돌아가 다른 노드를 탐색하는 방식입니다. 일반적으로 스택 구조를 이용하여 구현합니다.

BFS (Breadth-First Search)

BFS는 너비 우선 탐색으로, 한 노드의 이웃 노드를 모두 탐색한 뒤, 다음 깊이의 노드를 탐색하는 방식입니다.
일반적으로 큐 구조를 이용하여 구현합니다.

문제 설명

다음은 DFS와 BFS를 사용하여 해결할 수 있는 예제 문제입니다.
문제: 주어진 그래프에서 두 노드가 연결되어 있는지 여부를 판별하시오.

입력

노드의 수 N (1 ≤ N ≤ 1000)
엣지의 수 E (1 ≤ E ≤ 10000)
각 엣지를 나타내는 두 노드의 쌍 (A, B)
쿼리 Q (두 노드가 연결되어 있는지 확인할 쿼리 수)
각 쿼리마다 연결 여부를 확인할 두 노드 X, Y

출력

각 쿼리에 대해 X와 Y가 연결되어 있으면 “YES”를, 아니면 “NO”를 출력합니다.

문제 해결 과정

1. 그래프 표현

그래프를 인접 리스트 형태로 표현할 수 있습니다. 연결된 노드들을 리스트에 추가하여 부존재 여부를 알 수 있도록 합니다.

2. DFS 구현

DFS를 재귀 호출을 통해 구현해보겠습니다. 방문한 노드를 확인하기 위해 boolean 배열을 사용하고,
주어진 노드에서 시작하여 목표 노드에 도달할 때까지 탐색합니다.


fun dfs(graph: List>, visited: BooleanArray, current: Int, target: Int): Boolean {
    if (current == target) return true
    visited[current] = true

    for (neighbor in graph[current]) {
        if (!visited[neighbor]) {
            if (dfs(graph, visited, neighbor, target)) return true
        }
    }
    return false
}

3. BFS 구현

BFS는 큐를 사용하여 구현합니다. 시작 노드를 큐에 추가하고, 큐에서 노드를 하나씩 꺼내어
모든 이웃 노드를 방문하여 목표 노드에 도달하는지 확인합니다.


fun bfs(graph: List>, start: Int, target: Int): Boolean {
    val queue: Queue = LinkedList()
    val visited = BooleanArray(graph.size)
    
    queue.offer(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val current = queue.poll()
        if (current == target) return true

        for (neighbor in graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true
                queue.offer(neighbor)
            }
        }
    }
    return false
}

4. 전체 코드

이제 그래프의 입력을 받고, DFS와 BFS를 통해 연결 여부를 판단하는 전체 코드를 작성해보겠습니다.


import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val e = scanner.nextInt()

    val graph = List(n) { mutableListOf() }

    for (i in 0 until e) {
        val a = scanner.nextInt() - 1
        val b = scanner.nextInt() - 1
        graph[a].add(b)
        graph[b].add(a)  // 무방향 그래프
    }

    val q = scanner.nextInt()
    for (i in 0 until q) {
        val x = scanner.nextInt() - 1
        val y = scanner.nextInt() - 1

        val visitedDFS = BooleanArray(n)
        val visitedBFS = BooleanArray(n)

        // DFS 검사
        val isConnectedDFS = dfs(graph, visitedDFS, x, y)
        // BFS 검사
        val isConnectedBFS = bfs(graph, x, y)

        println("DFS에서의 연결: ${if (isConnectedDFS) "YES" else "NO"}")
        println("BFS에서의 연결: ${if (isConnectedBFS) "YES" else "NO"}")
    }
}

결론

DFS와 BFS는 각각 장단점이 있으며, 특정 문제에 따라 적합한 알고리즘을 선택하는 것이 중요합니다.
이 강좌를 통해 두 가지 알고리즘의 이해를 돕고, 실제 코딩테스트에서 활용할 수 있도록 준비하는 데 도움이 되었기를 바랍니다.

소개