코딩 테스트에서 자주 등장하는 알고리즘 중 DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 및 트리 탐색을 위한 기본적인 방법론입니다. 본 강좌에서는 이 두 가지 알고리즘을 스위프트로 구현하고, 이를 활용한 문제 풀이를 진행해보겠습니다.
1. DFS와 BFS 개요
DFS(Depth-First Search)는 한 경로를 끝까지 탐색한 후, 다음 경로를 탐색하는 방식입니다. 이를 위해 스택을 사용하며, 재귀적으로 호출하기도 합니다.
BFS(Breadth-First Search)는 시작 노드에서 인접한 노드를 탐색한 뒤, 다음 깊이의 노드를 탐색하는 방식입니다. 주로 큐를 사용하여 구현합니다.
2. 문제: 연결 요소의 개수 구하기
주어진 무방향 그래프에서 연결 요소의 개수를 구하는 문제를 다뤄보겠습니다. 그래프는 정점과 간선으로 이루어져 있으며, 연결된 정점의 개수를 찾는 것이 목표입니다.
문제 정의
정수 n (1 ≤ n ≤ 1000): 정점의 개수
리스트 edges: 각 간선이 연결하는 두 정점을 나타내는 (a, b)의 튜플입니다.
연결 요소의 개수를 반환하세요.
입력 예시
n = 5
edges = [(1, 2), (2, 3), (4, 5)]
출력 예시
2
3. 알고리즘 설명
이 문제를 해결하기 위해 DFS와 BFS 방식 모두 사용할 수 있습니다. 여기서는 DFS를 사용하여 해결해보겠습니다. 다음의 절차로 진행됩니다:
- 그래프를 인접 리스트 형태로 변환합니다.
- 방문 여부를 체크하기 위한 배열을 생성합니다.
- 모든 정점에 대해 방문하지 않은 정점이 있으면 DFS를 실행하고, 호출된 DFS 내에서 모든 연결된 정점을 방문 처리합니다.
- DFS가 호출 될 때마다 연결 요소의 개수를 하나씩 증가시킵니다.
4. 스위프트 구현
문제를 스위프트로 구현해보겠습니다.
import Foundation
var graph = [[Int]]()
var visited: [Bool] = []
var connectedComponents = 0
// DFS 함수 정의
func dfs(node: Int) {
visited[node] = true
for neighbor in graph[node] {
if !visited[neighbor] {
dfs(node: neighbor)
}
}
}
// 메인 함수
func connectedComponentsCount(n: Int, edges: [(Int, Int)]) -> Int {
graph = Array(repeating: [Int](), count: n + 1)
visited = Array(repeating: false, count: n + 1)
// 그래프 생성
for edge in edges {
let (a, b) = edge
graph[a].append(b)
graph[b].append(a)
}
for i in 1...n {
if !visited[i] {
dfs(node: i)
connectedComponents += 1 // 새로운 연결 요소 발견
}
}
return connectedComponents
}
// 사용 예시
let n = 5
let edges = [(1, 2), (2, 3), (4, 5)]
let result = connectedComponentsCount(n: n, edges: edges)
print("연결 요소의 개수: \(result)") // 출력: 연결 요소의 개수: 2
5. 알고리즘 분석
위의 알고리즘은 DFS를 이용하여 그래프를 탐색하기 때문에 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 개수, E는 간선의 개수입니다. 이 알고리즘은 각 정점을 한 번씩 방문하고, 각 간선도 한 번씩 검사하기 때문입니다.
6. 결론
본 강좌에서는 DFS를 이용하여 연결 요소의 개수를 구하는 알고리즘을 소개했습니다. DFS와 BFS는 모두 그래프 탐색에 있어 중요한 기법이므로, 각 알고리즘의 특성과 구현 방식을 충분히 이해하고 연습하는 것이 중요합니다. 다음 강좌에서는 BFS를 사용한 유사한 문제를 다뤄볼 예정입니다.