테스트 예제 3
•
다음과 같은 조건으로 최소의 비용으로 목적지까지 가는 알고리즘을 작성함.
•
산출을 하기 위해 크루스칼 알고리즘 기반으로 구현함.
•
홍길동 학생이 역에서 가천대학교 글로벌캠퍼스역으로 가려고 함. 이를 위해 여러 지하철 및 버스
환승역을 거쳐 가야함. 출발지에서 목적지까지 가야 할 때 최소의 비용으로 갈 수 있는 경로를
산출해야함.
입력 조건
•
N개의 역이 주어짐 (1 <= N <= 10)
•
N개의 역위치에는 비용 값이 주어짐.
•
한 번 연결된 간선은 두 번 이상 연결 될 필요 없음.
ex) (A, B), (B, A) → (A, B)
출력 조건
출발지에서 목적지까지 가는 최소 비용의 경로를 찾아 출력을 해야 함.
입력 예시
A B C D E F G
(7, 'A', 'B'),
(15, 'A', 'C'),
(8, 'B', 'C'),
(9, 'B', 'D'),
(8, 'C', 'D'),
(11, 'D', 'E'),
(6, 'D', 'F'),
(8, 'E', 'F'),
(4, 'E', 'G'),
(7, 'F', 'G')
출력 예시
[(4, 'E', 'G'), (6, 'D', 'F'), (7, 'A', 'B'), (7, 'F', 'G'), (8, 'B', 'C'), (8, 'C', 'D')]
문제 해결 아이디어
크루스칼 알고리즘을 활용한 최소 신장트리를 구현한다.
- 처음 부모 테이블을 자기 자신으로 초기화 후, 간선 정보를 비용에 따라 오름차순으로 정렬한다.
- Union 연산으로 각 노드별 부모 노드를 확인하여 사이클 발생 여부를 체크한다.
- 노드별 부모 테이블 값이 모두 같이 업데이트 되면, 최소 신장 트리에 포함된 간선들을 출력한다.
시간 복잡도
→ N은 간선(Edge)의 개수이며, 간선을 정렬하는 부분이 가장 오래걸린다.
간선의 수가 많아질 수록 정렬 과정이 성능에 더 큰 영향을 미친다.
코드
import sys
stations = input().split()
edges = []
# 부모 테이블 초기화
parent = {}
for station in stations:
parent[station] = station
# find 연산
def find_parent(parent, x):
# 부모 노드가 본인이 아닐 경우
if parent[x] != x:
# 부모 노드의 값을 넣기 위해 재귀적 수행.
parent[x] = find_parent(parent, parent[x])
return parent[x]
# union 연산
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
total_cost = 0
while True:
e_input = input()
if not e_input: # 공백 문자열일 경우 break
break
cost, a, b = e_input.split()
edges.append((int(cost), a, b))
edges.sort(key= lambda x:x[0])
min_cost_path = []
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
min_cost_path.append(edge)
print(min_cost_path)
Python
복사