이 문제는 이것이 코딩테스트다. 259페이지 문제이다. 이 문제는 E,V(간선,노드)가 100이하로 작다. 전형적인 플로이드 워셜문제이다. 일반적으로 500정도면 플로이드워셜을 사용하여도 된다. 아래는 나의코드이다. import sys INF = int(1e9) companyNum,wayNum = map(int,sys.stdin.readline().split()) myMap= [[INF]*(companyNum+1) for _ in range(companyNum+1)] for i in range(1,companyNum+1): myMap[i][i]=0 for _ in range(wayNum): temp=list(map(int,sys.stdin.readline().split())) myMap[temp[0]][..
플로이드 워셜
최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립되어 있다. 예를 들면 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등의 다양한 사례가 존재한다. 상황에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. 대표적으로 사용하는 최단 거리 알고리즘은 3가지인데 다익스트라(데이크스트라), 플로이드 워셜, 벨만 포드 알고리즘 이다. 이중 다익스트라와, 플로이드 워셜은 꼭 알아야 한다. 이 두가지에 대해서 설명을 하고 추후에 벨만 포드 알고리즘에 대해서 포스팅하겠다. 다익스..
