문제 설명
주어진 그래프에서 연결 요소의 개수를 구하는 문제입니다. 연결 요소란, 그래프에서 서로 연결된 정점들의 집합을 의미합니다. 예를 들어, A와 B가 연결되어 있고, B와 C가 연결되어 있다면, A, B, C는 하나의 연결 요소로 간주됩니다. 이 문제는 DFS(Depth First Search) 또는 BFS(Breadth First Search) 같은 그래프 탐색 기법을 사용하여 해결할 수 있습니다.
입력 형식
첫 번째 줄에 정점의 개수 N(1 ≤ N ≤ 1000)과 간선의 개수 M(0 ≤ M ≤ 100,000)이 주어진다.
그 다음 M개의 줄에는 각 간선의 정보가 주어진다. 각 간선은 두 정점의 쌍으로 표현된다.
출력 형식
연결 요소의 개수를 출력한다.
예시
입력
5 3
1 2
2 3
4 5
출력
2
위의 예시에서 1, 2, 3은 하나의 연결 요소를 이루고 4, 5는 또 다른 연결 요소를 이루므로 총 2개의 연결 요소가 있다.
문제 해결 과정
이 문제를 해결하기 위해 스위프트로 DFS를 구현하여 연결 요소를 계산해보겠습니다.
1. 그래프 표현
입력을 기반으로 그래프를 인접 리스트 형태로 표현합니다. 인접 리스트는 각 정점에 연결된 정점들을 리스트로 저장하는 방법입니다. 이 방법을 사용하면 메모리 사용량이 적고, 탐색하기 쉽게 됩니다.
2. DFS 구현
DFS 알고리즘을 사용하여 탐색을 수행합니다. 방문한 정점은 스택을 사용하여 추적합니다. 만약 현재 정점이 아직 방문되지 않았다면, 이를 방문한 것으로 표시하고, 연결된 정점들을 모두 DFS로 탐색합니다. 이렇게 방문하면 하나의 연결 요소가 끝난 것입니다.
3. 연결 요소 수 카운트
그래프의 모든 정점을 방문할 때마다 새로운 연결 요소가 발견될 때마다 카운트를 증가시킵니다. 모든 정점을 방문한 후 최종적으로 카운트된 값을 출력합니다.
4. 스위프트로 구현하기
import Foundation
// 그래프를 표현하기 위한 구조체
class Graph {
var adjacencyList: [[Int]]
var visited: [Bool]
var vertexCount: Int
init(vertexCount: Int) {
self.vertexCount = vertexCount
self.adjacencyList = Array(repeating: [], count: vertexCount + 1)
self.visited = Array(repeating: false, count: vertexCount + 1)
}
func addEdge(_ u: Int, _ v: Int) {
adjacencyList[u].append(v)
adjacencyList[v].append(u) // 무향 그래프
}
func dfs(_ vertex: Int) {
visited[vertex] = true // 현재 정점 방문 표시
for neighbor in adjacencyList[vertex] {
if !visited[neighbor] {
dfs(neighbor) // 재귀 호출
}
}
}
func countConnectedComponents() -> Int {
var componentCount = 0
for vertex in 1...vertexCount {
if !visited[vertex] {
dfs(vertex) // 새로운 연결 요소 발견
componentCount += 1
}
}
return componentCount
}
}
// 입력 받기
let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let n = firstLine[0]
let m = firstLine[1]
let graph = Graph(vertexCount: n)
for _ in 0..
시간 복잡도
이 알고리즘의 시간 복잡도는 O(N + M)입니다. N은 정점의 개수, M은 간선의 개수입니다. 모든 정점을 방문하고 모든 간선을 탐색하기 때문입니다. 이 시간 복잡도는 DFS 또는 BFS 알고리즘의 일반적인 성능입니다.
결론
연결 요소의 개수를 구하는 문제는 DFS나 BFS 같은 그래프 탐색 기법을 사용하여 효과적으로 해결할 수 있습니다. 이 문제를 통해 그래프의 기본적인 개념을 다루고, 스위프트를 사용하여 실제로 코드를 구현해보는 기회를 가졌습니다. 알고리즘을 구현하는 과정에서 데이터 구조와 알고리즘에 대한 이해도가 더욱 깊어졌기를 바랍니다.