[이코테] 최단 경로_전보 (python)

문제

나의 풀이

1. 개선된 다익스트라 풀이(우선순위 큐)

import heapq

# 도시 개수 n, 경로 개수 m, 메시지를 보낸 도시 c
n, m, c = map(int, input().split())
# 한 도시에서 다른 도시로 가는 시간 list
city = [list(map(int, input().split())) for _ in range(m)]

INF = int(1e9) # 무한을 의미하는 값 10억 설정

# 각 도시에 연결되어 있는 도시에 대한 정보를 담을 list 설정
graph = [[] for _ in range(n + 1)]
# 최단 시간 테이블을 모두 무한으로 초기화
time = [INF] * (n + 1)

# 모든 연결 정보를 저장
# i[0]: 출발 도시, i[1]: 도착 도시, i[2]: 소요 시간
# 꼭 append 함수를 쓸 것!
for i in city:
	graph[i[0]].append((i[1], i[2]))
    
def dijkstra(start):
	q = []
	# 시작 도시로 가기 위한 최단 시간은 0으로 설정하여 큐에 삽입
	heapq.heappush(q, (0, start))
	time[start] = 0
	
	while q: # 큐가 비어있지 않다면
		# 가장 최단 시간이 짧은 도시에 대한 정보 꺼내기
		t, now = heapq.heappop(q)
		# 현재 도시가 이미 처리된 적 있다면(즉, 이미 최단 시간이라면), 무시
		if time[now] < t:
			continue
            
		# 현재 도시와 연결된 다른 인접 도시들을 확인
		for j in graph[now]:
			# 현재 도시까지의 최단 시간(t) 
            # + 현재 도시에서 다른 도시(j[0])까지 걸리는 시간(j[1])
			cost = t + j[1]
			# 현재 도시를 거쳐서 다른 도시로 가는 시간이 더 짧은 경우
			if cost < time[j[0]]:
				time[j[0]] = cost # 더 짧은 시간으로 갱신
				# j[0]으로 가기 위한 최단 시간은 cost로 설정하여 큐에 삽입
				heapq.heappush(q, (cost, j[0]))
	
	time_no_INF = [i for i in time if i != INF] # time list에서 무한을 삭제한 list 생성
    # 출발 도시가 보낸 메시지를 받는 도시의 총 개수(출발 도시는 제외하기 위해 -1을 함)
	city_n = len(time_no_INF) - 1
    # 메시지를 받는데 총 걸리는 시간(즉, 출발 도시에서 가장 오랜 시간이 걸리는 경우)
	time_sum = max(time_no_INF)
    
	return print(city_n, time_sum, sep = ' ')
    
dijkstra(c)

2. 플로이드 워셜 알고리즘 풀이

# 도시(노드) 개수 n, 경로(간선) 개수 m, 메시지를 보낸 도시(출발지) c
n, m, c = map(int, input().split())
# 한 도시에서 다른 도시로 가는 시간 list
city = [list(map(int, input().split())) for _ in range(m)]

INF = int(1e9) # 무한을 의미하는 값 10억 설정

# 각 도시에 연결되어 있는 도시에 대한 정보를 담을 2차원 list 설정하고, 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에게 가는 시간 = 0 으로 초기화
for i in range(1, n + 1):
	graph[i][i] = 0
    
# 모든 연결 정보를 저장
# i[0]: 출발 도시, i[1]: 도착 도시, i[2]: 소요 시간
for i in city:
	graph[i[0]][i[1]] = i[2]
    
# 플로이드 워셜 알고리즘 수행
# 점화식: D_ab = min(D_ab, D_ak + D_kb)
for k in range(1, n + 1):  # 도시 개수가 n개 이므로, 1~n 범위 설정
	for a in range(1, n + 1):
		for b in range(1, n + 1):
			# a에서 b로 가는 시간 
            # = a에서 b로 가는 시간과 a에서 k를 거쳐 b로 가는 시간 중 짧은 시간
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
graph_c_no_INF = [i for i in graph[c] if i != INF] # graph list에서 무한을 삭제한 list 생성
# 출발 도시가 보낸 메시지를 받는 도시의 총 개수(출발 도시는 제외하기 위해 -1을 함)
city_n = len(graph_c_no_INF) - 1
# 메시지를 받는데 총 걸리는 시간(즉, 출발 도시에서 가장 오랜 시간이 걸리는 경우)
time_sum = max(*graph_c_no_INF)

print(city_n, time_sum, sep = ' ')

: 플로이드 워셜 알고리즘은 시간 복잡도가 O(N^3)이기 때문에, 아마 이 문제는 시간초과가 날 것이다.. 그치만 코드가 궁금해서 풀어봄!