네카라쿠배 (1) 썸네일형 리스트형 백준 10159번(JAVA) 플로이드-와샬 알고리즘을 이용하는 문제이다. 플로이드-와샬 알고리즘은 최단거리를 찾는 문제에서 가장 간단하다. 3중for문, 이것만 기억하면 된다. 3중for문이니까 당연히 시간복잡도는 O(v^3)이다. 그래서 보통 플로이드-와샬 알고리즘을 사용하는 문제들은 정점의 수가 1000을 넘지 않는 것 같다. 플로이드-와샬 알고리즘에 대한 기본적인 설명은 따로 하지 않겠다. 이 문제에서는 일단 입력을 받을때 1 2 이렇게 받으면 map[1][2]=1, map[2][1]=2 이렇게 했다. 1의 값은 앞에인덱스가 뒤에 인덱스보다 무겁다는 뜻, 2의 값은 앞에 인덱스가 뒤의 인덱스보다 보다 가볍다는뜻이다. 플로이드-와샬 알고리즘을 사용할때 기준점이 되는 k인덱스를 기준으로 map[i][k]==1&&map[k][j]=.. 이전 1 다음