[PS] DFS(깊이 우선 탐색)

Hood·2024년 11월 16일

DFS ps

PS

목록 보기

5/15

✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘

소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 Kotlin을 기반으로 작성하였습니다.

그래프 이론과 탐색

PS 문제를 풀다 보면 좌표, 위치, 연결 관계를 기준으로 상황이 주어지는 경우가 많습니다.
예를 들어 어떤 지점에서 다른 지점으로 이동할 수 있는지,
특정 위치까지 도달할 수 있는지,
연결된 구역의 개수를 구해야 하는 문제가 자주 등장합니다.

이럴 때 유용하게 사용할 수 있는 개념이 바로 그래프 이론과 그래프 탐색입니다.

그래프

그래프에 대해서는 비선형적 자료구조 포스트에서 한 번 다룬 적이 있습니다.
다시 정리하면, 그래프는 노드(Node)와 엣지(Edge)로 이루어진 자료구조입니다.

노드는 그래프를 이루는 기본 단위이며, 하나의 지점이나 개체를 나타냅니다.
엣지는 노드와 노드 사이의 연결 관계를 나타냅니다.

예를 들어 문제에서 여러 장소가 주어지고,
장소 사이를 이동할 수 있는 길이 있다면 다음과 같이 생각할 수 있습니다.

장소 → 노드
길 → 엣지

즉, 문제 속 상황을 그래프로 바꾸어 생각하면
훨씬 쉽게 접근할 수 있는 경우가 많습니다.

여기서 중요한 점은 방향성입니다.
엣지에 방향이 있다면 한쪽으로만 이동할 수 있고,
방향이 없다면 양방향 이동이 가능하다고 해석할 수 있습니다.

또한 모든 노드가 반드시 연결되어 있는 것도 아닙니다.
어떤 노드는 엣지가 하나도 없을 수도 있습니다.

따라서 그래프 문제를 풀 때는
문제에서 방향 그래프인지, 무방향 그래프인지,
그리고 연결 관계가 어떻게 주어지는지를 꼼꼼히 확인하는 것이 중요합니다.

DFS (Depth First Search)

그래프를 순회해야 하는 문제에서는 대표적으로
DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 사용합니다.
이번 글에서는 먼저 DFS를 살펴보겠습니다.

DFS는 말 그대로 깊이 우선 탐색입니다.
시작 노드에서 출발한 뒤, 갈 수 있는 곳을 최대한 깊게 들어가며 탐색하고,
더 이상 갈 곳이 없을 때 이전 위치로 돌아와 다음 경로를 탐색하는 방식입니다.

쉽게 말하면,

현재 노드를 방문합니다.
방문할 수 있는 인접 노드로 이동합니다.
그 노드에서도 다시 가장 먼저 갈 수 있는 곳으로 이동합니다.
더 이상 갈 곳이 없으면 되돌아옵니다.
아직 방문하지 않은 다른 경로를 계속 탐색합니다.

예를 들어보겠습니다.

위와 같이 노드와 엣지로 이루어진 그래프가 있다고 가정해 보겠습니다.
이 그래프에서 DFS를 수행하면, 현재 노드에서 갈 수 있는 가장 앞의 노드부터 깊게 탐색하게 됩니다.

예를 들어 1번 노드에서 시작한다면,
1과 연결된 노드 중 하나로 이동하고,
그다음에도 다시 연결된 노드로 계속 들어가며 탐색합니다.

이때 이미 방문한 노드를 또 방문하면 무한히 반복될 수 있으므로
방문 여부를 기록하는 배열이 꼭 필요합니다.

그리고 한 가지 더 기억해야 할 점은,
DFS의 방문 순서는 인접 노드를 어떤 순서로 저장했는지에 따라 달라질 수 있다는 것입니다.
즉, 그래프가 같더라도 인접 리스트의 순서가 다르면 탐색 결과도 달라질 수 있습니다.

in Kotlin

그렇다면 DFS를 Kotlin에서는 어떻게 구현할 수 있을까요?

그래프는 보통 인접 리스트 형태로 많이 구현합니다.
배열의 인덱스를 노드 번호로 사용하고,
각 인덱스에는 해당 노드와 연결된 인접 노드들을 저장하면 됩니다.

아래 예시에서는 편의를 위해 0번 노드는 사용하지 않고,
1번부터 7번까지의 노드를 사용하겠습니다.

fun main() {
    val graph = arrayOf(
        intArrayOf(),          // 0번 노드(사용하지 않음)
        intArrayOf(2, 3, 4),
        intArrayOf(1, 3, 5),
        intArrayOf(1, 2, 4),
        intArrayOf(1, 3, 6),
        intArrayOf(2, 6),
        intArrayOf(4, 5, 7),
        intArrayOf(6)
    )
}

깊이 우선 탐색은 재귀 함수로 구현하는 경우가 많습니다.
현재 노드를 방문한 뒤, 연결된 인접 노드들에 대해 같은 함수를 다시 호출하는 방식입니다.

이때 중요한 점은 현재 노드를 방문 처리한 뒤 탐색을 시작해야 한다는 것입니다.

fun main() {
    val graph = arrayOf(
        intArrayOf(),
        intArrayOf(2, 3, 4),
        intArrayOf(1, 3, 5),
        intArrayOf(1, 2, 4),
        intArrayOf(1, 3, 6),
        intArrayOf(2, 6),
        intArrayOf(4, 5, 7),
        intArrayOf(6)
    )

    val visited = BooleanArray(8)

    fun dfs(node: Int) {
        visited[node] = true
        println(node)

        for (next in graph[node]) {
            if (!visited[next]) {
                dfs(next)
            }
        }
    }

    dfs(1)
}

이 코드는 다음과 같은 흐름으로 동작합니다.

현재 노드를 방문 처리합니다.
현재 노드 번호를 출력합니다.
현재 노드와 연결된 인접 노드를 하나씩 확인합니다.
아직 방문하지 않은 노드라면 재귀적으로 DFS를 수행합니다.

위처럼 dfs(1)을 호출하면
1번 노드부터 시작해서 연결된 모든 노드를 깊이 우선으로 탐색하게 됩니다.

성공적으로 순회가 이루어지는 것을 확인할 수 있습니다.

주의! 스택 오버플로우

DFS를 재귀 함수로 구현하면 코드가 간단하고 직관적이라는 장점이 있습니다.
하지만 재귀 호출이 너무 깊어지면 스택 오버플로우(Stack Overflow) 가 발생할 수 있습니다.

재귀 함수는 호출될 때마다 함수 정보가 스택 메모리에 쌓입니다.
따라서 노드 수가 매우 많거나, 그래프의 깊이가 깊은 경우에는
스택에 너무 많은 호출이 쌓여 오류가 발생할 수 있습니다.

스택 오버플로우란?

스택 영역의 메모리가 허용된 범위를 넘어설 때 발생하는 오류입니다.

예를 들어 다음과 같은 경우에 발생할 수 있습니다.

재귀 함수를 너무 깊게 호출한 경우
종료 조건 없이 재귀가 반복되는 경우
함수 내부에 너무 큰 지역 변수를 선언한 경우

PS에서는 특히 재귀 DFS를 사용할 때 이 문제를 주의해야 합니다.

어떻게 해결할 수 있을까?

실제로 PS에서는 다음과 같은 방법을 많이 사용합니다.

반복문 + 스택 자료구조로 DFS를 직접 구현합니다.
재귀 대신 Stack 또는 ArrayDeque를 사용하면 스택 오버플로우 위험을 줄일 수 있습니다.
불필요하게 큰 지역 변수 사용을 줄입니다.
재귀 깊이가 매우 깊을 것으로 예상되면 반복 방식으로 전환합니다.

일반적인 알고리즘 문제 풀이에서는
컴파일러 옵션으로 스택 크기를 조정하기보다,
반복형 DFS로 바꾸는 방법이 더 현실적이고 안전한 해결법입니다.