BOJ 11404 플로이드

11404번: 플로이드 (acmicpc.net)

11404번: 플로이드

플로이드-워셜 알고리즘을 가장 대표할 수 있는 문제다.

 

플로이드-워셜 알고리즘은 향후 블로그에서 다룰거지만 그래프 탐색에서 한 지점에서 다른 지점으로 갈 수 있는 모든 최단 거리를 알고 싶을 때 사용하는 알고리즘으로

 

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]);
     }
   }
}

을 통해 각 지점간의 최단 거리를 구했다.