-
BOJ 11404 플로이드알고리즘/백준 2022. 1. 20. 23:21
플로이드-워셜 알고리즘을 가장 대표할 수 있는 문제다.
플로이드-워셜 알고리즘은 향후 블로그에서 다룰거지만 그래프 탐색에서 한 지점에서 다른 지점으로 갈 수 있는 모든 최단 거리를 알고 싶을 때 사용하는 알고리즘으로
O(N^3)의 시간 복잡도를 가지고 있으므로, 현재 보이는 n의 크기가 100 이상을 넘어가게 되면 사용하는 것이 까다롭다.
여기서 중요한 점은 한 지점에서 같은 지점으로 가는 버스는 없고, 한 지점에서 다른 지점으로 가는 경우의 수가 중복될 수도 있기 때문에 이 중에서 최단 거리를 찾아야한다.
최초 입력을 받기 전 배열을 초기화하기 위해서 갈 수 없는 거리에 대해서 INF 처리를 해주었다.
(INF = 987654321인데, 현 문제에서 절대로 도달할 수 없는 수이다. )
또한, 같은 지점끼리는 값 0을 배정했다. 이유는 본인의 지점에서 본인의 지점으로 가는 가장 최단 거리는 움직이지 않는 것이기 때문이다.
그 후 최초 입력을 받을 때
line[s][e] = Math.min(line[s][e], d);
해당 형식으로 혹시나 지점이 중복되서 들어올 경우 가장 짧은 거리를 찾아내기 위해 해당 코드를 사용했다.
이 외에는 플로이드-워셜 알고리즘을 통해서
for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { for ( int k = 1; k <= n; k++) { line[j][k] = Math.min(line[j][k], line[j][i] + line[i][k]); } } }
을 통해 각 지점간의 최단 거리를 구했다.
'알고리즘 > 백준' 카테고리의 다른 글
BOJ 21921 블로그 (0) 2022.02.11 BOJ 1238 파티 (0) 2022.01.28 BOJ 9177 단어 섞기 (0) 2022.01.26 BOJ 1613 역사 (0) 2022.01.21 BOJ 11051 이항 계수 2 (0) 2021.12.27