[이코테] 최단경로 예제

[이코테] 최단경로 예제

1. 미래도시

Level 2

문제 링크(페이지) : 이코테 259p

방문판매원 A가 1번 회사에서 출발해 K 회사에서 소개팅을 하고 특정 회사 X로 가고자 할 때, 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성해라.

문제 풀이

전형적인 플로이드 워셜 알고리즘 문제

(다른 알고리즘도 가능하나 입력 N범위가 100이하로 작기 때문에 구현이 쉽고 간단한 플로이드 워셜이 유리)

1번 회사에서 K까지의 최단거리에 K회사에서 X로 가는 최단거리를 더해 구한다.

코드

INF = int(1e9) n, m = map(int, input().split()) # 2차원 리스트 만들기 graph = [[INF]*(n+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, n+1): if i == j: graph[i][j] = 0 # 연결된 도로는 1로 for _ in range(m): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 x, k = map(int, input().split()) # 플로이드 워셜 알고리즘 for k in range(1, n+1): for i in range(1, n+1): for j in range(1, n+1): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][i]) distance = graph[1][k] + graph[k][x] if distance >= INF: # 도달할 수 없는 경우 print("-1") else: print(distance)

2. 전보

Level 3

문제 링크(페이지) : 이코테 262p

통로가 연결된 도시는 메시지를 보낼 수 있다.

예를 들어 A에서 B로 향하는 통로가 있다면 메시지 전송이 가능하다.

하지만 B에서 A로 향하는 통로가 없다면 메시지 전송은 불가하다.

도시의 개수, 통로의 개수, 메시지를 보내고자 하는 도시가 주어질 때, 도시 C에서 보낸 메시지를 받게되는 도시는 몇 개인지 얼마나 시간이 소요되는지를 계산하는 프로그램을 작성해라.

문제 풀이

한 도시에서 특정 다른 도시로의 최단 거리를 구하는 다익스트라 알고리즘을 이용또한 입력 데이터의 범위가 크기 때문에 힙을 이용해 구현한다.

코드

import heapq import sys input = sys.stdin.readline #입력 데이터의 범위가 넓기 때문 INF = int(1e9) n, m, c = map(int, input().split()) # 각 노드가 연결된 노드 기록 graph = [[] for i in range(n+1)] # 최단 거리를 저장할 리스트 초기화 distance = [INF] * (n+1) for _ in range(m): x, y, z = map(int, input().split()) graph[x].append((y, z)) # x에서 y로 가는 비용은 z임을 graph에 추가 # 다익스트라 알고리즘 def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) dijkstra(c) count = 0 max_distance = 0 for d in distance: # 도달할 수 있는 노드 중 가장 멀리 있는 노드 확인 if d != INF: count += 1 max_distance = max(max_distance, d) print(count - 1, max_distance)

from http://shotory.tistory.com/53 by ccl(A) rewrite - 2021-12-28 22:26:39