테스트 예제 4
•
다음과 같은 조건으로 최소비용 및 최단경로로 목적지까지 가는 알고리즘을 작성해야 함.
•
산출을 하기 위해 다익스트라 알고리즘 기반으로 구현 함.
•
홍길동 학생이 친구들과 오랜만에 즐거운 저녁식사 시간을 가천대학교 역 근처에서 가짐. 생각보다 식사시간이 길어지고 비용을 아끼기 위해 지하철역을 선택하여 집에 가는 것으로 결정하였음. 가장 빠르고 비용을 아낄 수 있는 최단경로로 가야 함.
입력조건
•
N개의 역이 주어짐 (1 <= N <= 10)
•
N개의 역위치에는 비용 값이 주어짐.
•
출발지(가천대학교)는 E노드이며 도착지는(홍길동 학생의 집)은 A노드 근처에 있음.
출력조건
각 노드와 간선을 연결하여 어떤 노드가 가장 빠른 지 경로를 출력해야 함.
입력 예시
역의 개수 : 5
'A': {'B': 3, 'C': 2},
'B': {'D': 7, 'E': 8},
'C': {'A': 2, 'D': 4, 'E':1},
'D': {'B': 7, 'C': 4},
'E': {'B': 8, 'C': 1}
→ 좀 더 정확한 구분을 위해 역의 개수, 인접 노드의 개수도 따로 입력받았습니다.
출력 예시
E->C->A
“Completed”
문제 해결 아이디어
다익스트라 알고리즘을 활용한 최단경로를 계산한다. 우선순위 큐를 활용한다.
- 각 노드를 우선순위 큐를 활용해서 꺼내고, 각 노드 별 인접노드를 조사한다.
- 거리 값이 업데이트 되는 노드만, 즉 최소 거리로 업데이트 되는 노트만 큐에 넣는다.
- 큐가 빌 때 까지 해당 과정을 반복한다.
- 최종적으로 도착 노드의 거리 값이 최소 거리가 된다.
시간 복잡도
→ 힙 작업(heappop 및 heappush)은 각각 O(logV) 시간이 걸린다. 다익스트라 알고리즘 루프는 최대 V번 실행되며(각 노드가 힙에 한 번씩 추가되므로), 루프 내에서는 힙 작업과 이웃 탐색이 최악의 경우 O(E)이다. 따라서 이 부분의 전체 시간 복잡도는 O(V * (logV + E))이다.
코드
import heapq
def dijkstra(graph, start, end):
# 최단 거리를 저장하는 딕셔너리
distances = {station: float('inf') for station in graph}
distances[start] = 0
# 우선순위 큐를 사용하여 최단 거리를 갱신하며 탐색
priority_queue = [(0, start)]
previous_nodes = {station: None for station in graph}
while priority_queue:
current_distance, current_station = heapq.heappop(priority_queue)
# 현재 노드가 이미 처리된 경우, 스킵
if current_distance > distances[current_station]:
continue
for neighbor, weight in graph[current_station].items():
distance = current_distance + weight
# 더 짧은 경로를 찾았을 경우 업데이트
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_station
heapq.heappush(priority_queue, (distance, neighbor))
path = []
current = end
while previous_nodes[current] is not None:
path.insert(0, current)
current = previous_nodes[current]
path.insert(0, start)
return path
def main():
# 사용자로부터 역과 비용 정보를 입력 받기
stations = {}
# 역(노드) 개수 입력
num_stations = int(input("전체 역 개수: "))
for _ in range(num_stations):
# 역 이름 입력
station_name = input("역 이름: ")
# 인접 역(노드) 개수 입력
num_neighbors = int(input("인접 역 개수: "))
neighbors = {}
for _ in range(num_neighbors):
# 인접 역 이름 입력
neighbor_name = input("인접 역 이름: ")
# 인접 역 까지 비용 정보 입력
neighbor_weight = int(input("인접 역 비용: "))
neighbors[neighbor_name] = neighbor_weight
stations[station_name] = neighbors
# 출발 역 및 도착 역 정보 입력
start_station = input("출발 역: ")
end_station = input("도착 역: ")
# 다익스트라 알고리즘 실행
result = dijkstra(stations, start_station, end_station)
# 결과 출력
if result[-1] == end_station:
print("->".join(result))
print("Completed")
else:
print("No Path")
if __name__ == "__main__":
main()
Python
복사