목록쿠팡맨 (1)

국문과 유목민

[최단경로] 미래도시

1. 문제 설명 미래도시 쿠팡맨이 N개의 도시들을 돌아다니면서 배달을 하는데, 특정 노드 (K) 를 지나서 노드 (X)에 도착하려고 할 때 몇 개의 도시를 지나가야 하는지를 묻는 문제이다. 각 도시와 도시가 연결된 간선의 비용은 1로 동일하다. - 전형적인 플로이드 워셜 알고리즘의 문제이다. - 플로이드 알고리즘의 경우 대칭행렬이 아니기 때문에 그냥 계산해도 양방향을 고려한 그래프가 된다. 2. 코드 # INF = int(1e9) n, m = map(int, input().split()) graph = [[INF]*(n+1) for _ in range(n+1)] for a in range(n+1): for b in range(n+1): if a==b: graph[a][b]=0 for _ in range(..
알고리즘_코딩테스트/이것이 코딩테스트다 2021. 12. 7. 23:41
이전 Prev 1 Next 다음