Swift로 DFS 탐색하기

DFS(Depth-First Search)는 그래프를 탐색하는 알고리즘 중 하나로, 깊이를 우선으로 탐색합니다. 이번 예제에서는 Swift 언어를 사용하여 DFS 탐색을 구현해보도록 하겠습니다.

그래프 구현하기

먼저, DFS 탐색을 수행할 그래프를 구현해야 합니다. 그래프는 노드(Node)와 간선(Edge)으로 이루어져 있으며, Swift에서는 일반적으로 인접 리스트(Adjacency List)를 사용하여 그래프를 표현합니다. 인접 리스트는 각 노드에 연결된 다른 노드들의 리스트를 저장하는 방식입니다.

 

class Graph {
    var adjacencyList: [Int: [Int]] = [:] // 인접 리스트
    
    func addEdge(_ u: Int, _ v: Int) {
        if adjacencyList[u] == nil {
            adjacencyList[u] = []
        }
        adjacencyList[u]?.append(v)
    }
}

위 코드에서 Graph 클래스는 adjacencyList 변수를 통해 인접 리스트를 관리합니다. addEdge 메서드는 두 노드 u와 v 사이에 간선을 추가하는 역할을 합니다. 만약 u에 대한 인접 리스트가 없다면, 먼저 리스트를 생성한 후 v를 추가합니다.

DFS 탐색 구현하기

이제 DFS 탐색을 구현해보겠습니다. DFS 탐색은 재귀적으로 구현하는 것이 일반적입니다. 재귀 함수를 통해 현재 노드를 방문하고, 해당 노드와 연결된 다른 노드들을 방문하는 과정을 반복합니다.

 

extension Graph {
    func dfs(_ startNode: Int) {
        var visited: [Bool] = Array(repeating: false, count: adjacencyList.count)
        dfsHelper(startNode, &visited)
    }
    
    private func dfsHelper(_ currentNode: Int, _ visited: inout [Bool]) {
        visited[currentNode] = true
        print("노드 \(currentNode)을(를) 방문했습니다.")
        
        if let neighbors = adjacencyList[currentNode] {
            for neighbor in neighbors {
                if !visited[neighbor] {
                    dfsHelper(neighbor, &visited)
                }
            }
        }
    }
}

위 코드에서 dfs 메서드는 DFS 탐색을 시작하는 역할을 합니다. 먼저, 방문한 노드를 기록하는 visited 배열을 초기화합니다. 그리고 dfsHelper 메서드를 호출하여 실제 탐색을 수행합니다.

dfsHelper 메서드는 현재 노드 currentNode를 방문하고, 해당 노드와 연결된 이웃 노드들을 확인하여 방문하지 않은 노드라면 dfsHelper를 재귀적으로 호출합니다. 이 과정을 통해 그래프를 탐색하게 됩니다.

예제 실행하기

이제 구현한 DFS 탐색을 예제를 통해 실행해보겠습니다.

let graph = Graph()
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(1, 2)
graph.addEdge(2, 0)
graph.addEdge(2, 3)
graph.addEdge(3, 3)

graph.dfs(2)

위 예제에서는 0부터 3까지의 노드와 해당 노드들 간의 간선을 추가하고, 노드 2를 시작으로 DFS 탐색을 수행합니다. 실행 결과는 다음과 같습니다.

 

노드 2을(를) 방문했습니다.
노드 0을(를) 방문했습니다.
노드 1을(를) 방문했습니다.
노드 3을(를) 방문했습니다.

DFS 탐색은 깊이 우선으로 탐색하기 때문에 2번 노드에서 시작하여 연결된 0, 1, 3 노드를 순서대로 방문한 것을 확인할 수 있습니다.

 

 

이상으로 Swift로 DFS 탐색을 구현하는 예제를 소개해드렸습니다. DFS 탐색은 그래프 문제를 해결하는데 많이 활용되므로, 알고리즘 학습에 많은 도움이 되리라 생각합니다.