Swift로 그래프 탐색 알고리즘을 실전 문제에 적용해보기 - DFS 편

그래프 탐색 알고리즘에 대한 이해가 선행되어야 한다. 그래프와 DFS/BFS의 개념을 모른다면 여기를 추천한다.

---

Depth-First Search (DFS) 

- 이번 시간에 할 것📍

- 깊이 우선 탐색

- 이번 포스팅에서는 weigh을 가지지 않는 방향 그래프에서 모든 경우를 구해볼 때 이 DFS를 사용할 것이다. 예를 들면 1부터 N까지의 자연수 중 n개의 집합을 만들 수 있을 때, 가능한 모든 순열을 구해야 할 때 사용할 수 있다.

- 스택을 통해 구현한다. 즉, 재귀함수를 통해 구현할 것이다. (함수가 호출되면 스택 영역에 쌓이게 된다. 함수가 무한호출될 때 Stack Overflow 가 발생하는 것도 여기서 기인하는 것.)

 

Breadth-First Search (BFS)

- 다음 시간에 할 것📍

- 너비 우선 탐색

- 다음 포스팅에서 weigh을 가지지 않는 방향 그래프에서 최단/최소 경로를 구해볼 때 이 BFS를 사용할 것이다. 예를 들면 A노드(A도시)에서 B노드(B도시)로 가기 위해서는 어떤 edge들을 선택해 어떤 노드들을 거쳐가는 것이 최소 경로인가(어떤 버스를 선택해 어떤 도시를 경유하는 것이 최소환승이 될 수 있는가?)의 문제가 있다.

- 큐를 통해 구현한다.

---

실제로 문제를 한 번 풀어보자.

 

1부터 시작해 N개의 노드를 가지는 방향 그래프가 주어진다. 1번 노드에서 시작하여 N번 노드로 가는 모든 경우의 수를 구하시오.

- 입력: N을 위한 자연수 n과 edge들의 연결 정보를 위한 (i, j) 배열. (i번 노드에서 j번 노드로 이어지는 edge가 존재한다)

- 출력: 1번에서 출발해 N번에 도착할 수 있는 경로의 모든 경우의 수

 

예를 들어 다음과 같은 입력이 주어진다고 치자.

• n: 5
• edge 정보: [(1, 2), (1, 3), (1, 4), (2, 1), (2, 4), (2, 5), (3, 2), (3, 4), (4, 5)]

그러면 아래와 같은 방향 그래프가 만들어질 것이다.

이때 1번 노드에서 5번 노드까지 갈 수 있는 경로는 여러 개가 있다.

• 1 - 2 - 4 - 5
• 1 - 2 - 5
• 1 - 3 - 2 - 4 - 5
• 1 - 3 - 2 - 5
• 1 - 3 - 4 - 5
• 1 - 4 - 5

따라서 기대하는 출력 결과는 6개가 될 것이다.

위 풀이를 코드가 아닌 손으로 하나씩 따라가며 해보자. 그러면 자연히 느끼게 되겠지만, 이렇게 모든 경우를 헤아려볼 때는 '끝까지 가보고, 빠꾸하고, 다음 경우를 끝까지 가보고, 빠꾸하고' 같은 플로우를 거치는 것이 효율적이다. 이런 과정에서 LIFO(Last-in, First-out)의 원리를 사용하는 자신을 발견할 것이다. 즉, 스택을 통한 깊이 우선 탐색(DFS)을 하는 것이다.

이 원리만 이해한다면 Node나 Edge 자료구조를 명시적으로 사용하지 않더라도 단순히 재귀함수로만 구현이 가능하다.

func practiceDFS(n lastNode: Int, edges: [(Int, Int)]) -> Int {
    var edgeInfo = [Int: Array<Int>]()
    // edge 정보를 setup
    for edge in edges {
        if var array = edgeInfo[edge.0] {
            array.append(edge.1)
            edgeInfo[edge.0] = array
        } else {
            edgeInfo[edge.0] = [edge.1]
        }
    }
    
    // 1. 궁극적으로 원하는 값 (재귀를 돌며 수집할 값)
    var result = 0
    
    func dfs(node: Int, visited: [Int]) {
        guard node != lastNode else {
        // 2. 재귀를 멈추는 조건
            result += 1
            return
        }
        guard let neighbors = edgeInfo[node] else { return }
        for edge in neighbors {
        // 현재의 노드에서 이동할 수 있는 노드 중, 아직 방문하지 않은 곳으로 가본다 (중복 방지)
            guard visited.contains(edge) == false else { continue }
            dfs(node: edge, visited: visited + [edge])
        }
    }
    
    // 3. 초기값으로 어떤 것을 넘길지
    dfs(node: 1, visited: [1])
    
    return result
}

practiceDFS(n: 5, edges: [(1, 2), (1, 3), (1, 4), (2, 1), (2, 4), (2, 5), (3, 2), (3, 4), (4, 5)])
// print "6"

 

손으로 풀었던 플로우를 그대로 코드에 옮겨 놓은 것이다. 포인트는 주석에 번호를 달아놓은 세 가지 부분이다.

• 1. 궁극적으로 구하고자 하는 값. 재귀 함수의 외부에 선언되었다. 재귀 함수를 돌며 특정 기준에 만족할 경우 이 값을 변경할 것이다. 우리의 예제가 요구하는 것은 "모든 경우의 수"이기 때문에, 코드에서의 result는 그 개수이다.
• 2. 재귀를 멈추는 조건. 재귀 함수를 돌다가 특정 조건(요구를 만족하는 조건)에 다다르면 재귀 함수를 종료한다. 우리의 예제에서는 재귀호출이 반복되는 과정에서 n번 노드에 도달한 경우 result 값을 1 더해주고 return한다.
• 3. 재귀함수를 호출할 때의 초기값. 어디서부터 연산을 시작할지는 중요하다. 우리의 예제에서는 항상 1번 노드에서 출발하기 때문에 위 코드와 같은 파라미터가 들어갔다.

DFS를 위한 재귀함수, 혹은 스택연산을 구현하고 위 세 기준만 적절히 설정한다면 이와 유사한 문제를 마찬가지로 해결할 수 있다.

---

연습해볼 겸 유사한 DFS 문제를 하나 더 풀어보자. 이번에는 '노드'나 '간선'이라는 표현이 없는 문제를 가져와보았다. 이런 문제 역시 DFS의 원리를 적용할 수 있다.

 

랜덤으로 n개의 자연수를 받아, m개로 구성된 가능한 Subset을 모두 출력해보자. (m <= n)

- 입력: n개의 자연수 배열과, Subset의 원소 개수가 될 자연수 m (배열의 원소들은 유니크함)

- 출력: m개로 구성된 가능한 Subset을 모두 출력

 

간단히 예를 들어보겠다. 입력으로 자연수 배열 [1, 2, 4]가 들어오고 m으로는 2가 들어왔다고 해보자. [1, 2, 4] 배열에서 2개를 뽑아 만들 수 있는 모든 순열을 나열해보면 다음과 같다.

• [1, 2]
• [1, 4]
• [2, 1]
• [2, 4]
• [4, 1]
• [4, 2]

총 6개의 경우의 수를 모두 나열하면 된다. [1, 2]와 [2, 1]이 서로 다르게 취급된다는 것에 유의하자.

이번 문제에서는 문제에 직접적으로 드러나있지 않은 Node와 Edge를 먼저 파악해야한다. Node는 입력받은 자연수 배열의 원소 각각이 될 것이다. Edge의 경우에는, 모든 노드가 다른 모든 노드에 연결되어 있다고 생각할 수 있다. [1, 2, 4] 배열로 생각해보면, 첫 번째 노드는 1, 2, 4 세 가지 중 하나가 될 수 있다. 이 중 1을 선택한 경우 (현재까지의 Subset은 {1}) 그 다음 노드는 2와 4 중 하나가 될 수 있다(2를 선택한 경우의 Subset은 {1, 2}이고, 4를 선택한 경우의 Subset은 {1, 4}가 되는 것).

이제 세 가지 중요한 기준을 정해보자.

• 1. 궁극적으로 구하고자 하는 값. 재귀 함수의 외부에 선언할 결과값은 Subset(m개의 원소로 구성된)들의 배열이 될 것이고, 우리는 모든 재귀함수가 종료되면 이 결과를 출력해줄 것이다.
• 2. 재귀를 멈추는 조건. 원소를 하나씩 더해나가다가, 선택된 Subset의 개수가 m개가 되었을 때 재귀를 종료할 것이다.
• 3. 재귀함수를 호출할 때의 초기값. 배열의 원소 중 어떤 원소라도 첫 번째 원소가 될 수 있도록 작성해야 한다. (재귀를 호출하며 첫 번째 원소를 고정하면 안 된다.)

이 기준을 따라 작성한 코드는 다음과 같다.

func practiceDFS(numbers: [Int], m: Int) {
    // 1
    var result = Array<[Int]>()
    
    func dfs(selected: [Int]) {
        guard selected.count < m else {
            // 2
            result.append(selected)
            return
        }
        for number in numbers {
            guard selected.contains(number) == false else { continue }
            dfs(selected: selected + [number])
        }
    }
    
    // 3
    dfs(selected: [])
    
    print(result)
}

practiceDFS(numbers: [1,2,4], m: 2)
// print "[[1, 2], [1, 4], [2, 1], [2, 4], [4, 1], [4, 2]]"

---

이번 포스트에서는 DFS의 원리를 이용해 실제로 코드에 적용하는 법을 알아보았다. 여기서는 재귀함수를 사용하는 방법만을 예제로 작성했지만 구현은 문제의 요구사항/조건 등에 따라 효율적인 방법을 적용할 수 있다. 물론 Node, Edge 등의 자료구조를 따로 이용한다면 더 간결하고 가독성있는 코드를 작성할 수 있다. 다음 시간에는 BFS를 다룰 것인데, 그때는 Node와 Edge 자료구조를 직접 만들어 문제 풀이에 사용해보겠다.