그래프는 맨날까먹어~ (#1197)
#1197 최소 스패닝 트리 (https://www.acmicpc.net/problem/1197)
오랜만에 풀었다.
그래프 문제풀이는 여러가지 개념이 필요한데... 하나씩 살펴보자
그래프를 어떻게 저장할 것인가?
그래프를 저장하는 방법은 세 가지가 있다.
인접행렬 > 인접리스트
인접행렬이 구현이 쉽다. 대신 그만큼 메모리와 시간을 많이 쓴다.
인접리스트는 비교적 메모리와 시간을 적게 쓴다.
사실, 가장 효율적인 방법은 우선순위 큐라고 할 수 있다. 다만 이는 저장 방법이 아니라, 탐색 방법이다.
우선순위 큐는 큐에 우선순위를 부여한 방식인데, 파이썬에서 이를 어떻게 구현할 수 있을까?
heapq라이브러리를 쓴다. 이는 최소힙을 구현한 자료구조로, 0번 인덱스에 있는 값을 기준으로 정렬된다고 생각하면 된다.
따라서 최소비용을 계산하기 위해 그래프를 저장한다면, (cost, node) 형태로 넣으면 된다. pop을 했을 때 cost가 작은 edge부터 return 된다.
1. 인접 행렬 (Adjacency Matrix)
• 설명: 정점 간의 연결 관계를 2차원 배열로 저장합니다. 행과 열의 교차점에 가중치를 넣습니다. 연결되지 않은 경우에는 보통 0이나 ∞로 표시합니다.
• 예시: 4개의 노드를 가진 가중치 그래프
# 인접 행렬로 그래프 표현
graph_matrix = [
[0, 1, 4, 0], # 노드 0: 1과 4는 가중치, 0은 연결되지 않음
[1, 0, 2, 5], # 노드 1: 1과 2와 5로 연결
[4, 2, 0, 1], # 노드 2: 4와 2와 1로 연결
[0, 5, 1, 0] # 노드 3: 5와 1로 연결
]
2. 인접 리스트 (Adjacency List)
• 설명: 각 노드에 연결된 노드와 가중치를 리스트로 저장합니다. 인접 리스트는 딕셔너리나 리스트의 리스트로 표현할 수 있습니다.
• 예시: 4개의 노드를 가진 가중치 그래프
# 인접 리스트로 그래프 표현
graph_list = {
0: [(1, 1), (2, 4)], # 노드 0: 노드 1과 가중치 1, 노드 2와 가중치 4
1: [(0, 1), (2, 2), (3, 5)], # 노드 1: 노드 0과 가중치 1, 노드 2와 가중치 2, 노드 3과 가중치 5
2: [(0, 4), (1, 2), (3, 1)], # 노드 2: 노드 0과 가중치 4, 노드 1과 가중치 2, 노드 3과 가중치 1
3: [(1, 5), (2, 1)] # 노드 3: 노드 1과 가중치 5, 노드 2와 가중치 1
}
3. [탐색방법] 우선순위 큐 (Priority Queue)
• 설명: 우선순위 큐 자체는 그래프를 저장하는 방식이 아니라, 다익스트라 알고리즘에서 최단 거리 계산 시 사용할 큐입니다. 다익스트라 알고리즘에서 사용할 때는 보통 튜플 (거리, 노드)를 형태로 힙큐에 저장합니다.
• 예시: heapq 모듈을 사용한 초기화 예시
import heapq
# 우선순위 큐 초기화
priority_queue = []
heapq.heappush(priority_queue, (0, 0)) # (거리, 노드) 형태, 예를 들어 시작 노드 0의 거리는 0방향이 있는가?
그래프가 단방향인지, 무방향인지 잘 판단해야한다.
별도의 언급이 없다면, 보통 무방향 그래프이다.
무방향 그래프라면, 양 방향으로 그래프를 탐색할 수 있는 것이다.
따라서 다음과 같이 start-end, end-start를 모두 저장해줘야한다.
방향이 있는 그래프라면 당연히 다음과 같이 해주면 된다.
최소신장트리를 어떻게 구현할 것인가?
이는 프림 알고리즘과 크루스칼 알고리즘이 있다. 상황에 따라 적절한걸 사용해주면 된다.
[FROM GPT]
1. 프림 알고리즘 (Prim’s Algorithm)
• 작동 방식: 시작 정점에서 시작하여 연결된 간선 중 최소 가중치 간선을 선택해 트리에 추가합니다. 트리에서 연결되지 않은 정점과 연결되는 간선들 중 최소 가중치 간선을 계속 선택하여 트리를 확장해 나갑니다.
• 시간복잡도:
• 우선순위 큐를 사용하여 구현할 때: O(E \log V)
• 인접 행렬을 사용하여 구현할 때: O(V^2)
• 인접 리스트를 사용하고, 힙 자료구조를 사용하는 경우 O((V + E) \log V)
• 적용 환경: 그래프가 밀집(dense)해 있는 경우(즉, 간선의 수 E가 많을 때) 효율적으로 동작합니다.
import heapq
def prim(graph, start):
mst_cost = 0 # MST의 총 비용
visited = set() # 방문한 정점을 추적
min_heap = [(0, start)] # (가중치, 정점) 형태로 초기화
while min_heap:
cost, u = heapq.heappop(min_heap)
if u in visited:
continue
# 현재 정점을 MST에 추가
mst_cost += cost
visited.add(u)
# 인접한 모든 정점을 탐색
for v, weight in graph[u]:
if v not in visited:
heapq.heappush(min_heap, (weight, v))
return mst_cost
# 예시 그래프 (인접 리스트)
graph = {
0: [(1, 4), (2, 3)],
1: [(0, 4), (2, 1), (3, 2)],
2: [(0, 3), (1, 1), (3, 4), (4, 3)],
3: [(1, 2), (2, 4), (4, 2)],
4: [(2, 3), (3, 2)]
}
# 시작 정점을 0으로 설정
mst_cost = prim(graph, 0)
print("Minimum Spanning Tree Cost (Prim):", mst_cost)
2. 크루스칼 알고리즘 (Kruskal’s Algorithm)
• 작동 방식: 모든 간선을 가중치 기준으로 오름차순 정렬한 후, 가장 작은 간선부터 선택합니다. 사이클이 생기지 않도록 확인하면서 트리에 추가하고, 트리에 포함된 간선의 개수가 V-1개가 될 때까지 반복합니다.
• 시간복잡도:
• 간선을 정렬하는 시간: O(E \log E)
• 유니온-파인드(Union-Find)를 통한 사이클 검사: O(E \log V)
• 전체 시간복잡도: O(E \log E) 또는 O(E \log V) (간선 정렬이 주 시간복잡도를 차지)
• 적용 환경: 그래프가 희소(sparse)해 있는 경우(즉, 간선의 수 E가 적을 때) 효율적으로 동작합니다.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def kruskal(n, edges):
# 간선들을 가중치 기준으로 정렬
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
mst_cost = 0
mst_edges = []
for u, v, weight in edges:
# 간선이 사이클을 형성하지 않으면 MST에 추가
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst_cost += weight
mst_edges.append((u, v, weight))
return mst_cost, mst_edges
# 예시 그래프 (간선 리스트)
# 각 간선은 (정점1, 정점2, 가중치) 형태로 나타냄
edges = [
(0, 1, 4),
(0, 2, 3),
(1, 2, 1),
(1, 3, 2),
(2, 3, 4),
(2, 4, 3),
(3, 4, 2)
]
# 정점 개수와 간선 리스트 전달
mst_cost, mst_edges = kruskal(5, edges)
print("Minimum Spanning Tree Cost (Kruskal):", mst_cost)
print("Edges in MST:", mst_edges)
시간복잡도 비교
• 그래프의 밀도에 따라 두 알고리즘 중 선택이 달라집니다.
• 밀집 그래프: O(E \log V)인 프림 알고리즘이 더 유리합니다. 간선의 수 E가 V^2에 가까워지기 때문에, 정렬 없이 바로 우선순위 큐를 이용해 빠르게 간선을 선택하는 것이 효과적입니다.
• 희소 그래프: O(E \log E)인 크루스칼 알고리즘이 더 적합합니다. 간선의 수가 적어 정렬의 부담이 크지 않으며, 각 간선을 하나씩 탐색하여 트리를 구축하는 방식이 효율적입니다.
따라서, 그래프의 밀집도와 구현 방식에 따라 프림과 크루스칼 알고리즘의 효율성 차이가 발생합니다.
그럼 다익스트라는 뭐냐고?
다익스트라는 특정 노드에서 특정 노드까지의 최단거리를 계산하는 그리디 알고리즘이다.
*(그리디 알고리즘 = 최적값만 찾는 알고리즘, 브루트포스와 상응하는 개념)
출발지점과 도착지점이 있다는 점에서, 프림/크루스칼과 차이가 있다.
그렇다. 그럼 이러한 개념들을 모두 고려한, 이 문제에 대한 답은 다음과 같다.
import sys, heapq
input = sys.stdin.readline
v, e = map(int, input().split())
graph = [[] for _ in range(v + 1)]
for _ in range(e):
start, end, edge = map(int, input().split())
# 무향그래프
graph[start].append([edge, end])
graph[end].append([edge, start])
answer = 0
visited = [False for _ in range(v + 1)]
min_heap = [(0, 1)]
# visited[1] = True
while min_heap:
edge, node = heapq.heappop(min_heap)
# 방문한 곳 처리
if visited[node]:
continue
# 방문처리
answer += edge
visited[node] = True
# 주변 엣지 탐색
for edge, next in graph[node]:
if not visited[next]:
heapq.heappush(min_heap, (edge, next))
print(answer)
처음에 틀려서 당황했는데, 무향그래프인점을 반영하지 않아서였다.