[c++] 백준 - 플로이드

플로이드 성공

시간 제한 메모리 제한 제출 정답맞은 사람 정답 비율

1 초

256 MB

29397

11487

8237

41.787%

알고리즘 분류

• 그래프 이론
• 플로이드–와샬

 

https://www.acmicpc.net/problem/11404

11404번: 플로이드

---

#include <iostream>
using namespace std;
const int MAX = 101;
const int INF = 987654321;
int n, m, a, b, c;
int Edge[MAX][MAX];

void Input(){
   cin>>n>>m;
   for(int i=1;i<=n;i++)
   {
      for(int j=1;j<=n;j++)
      {
         Edge[i][j] = INF; //간선 무한대로 초기화
      }
   }

   for(int i=0;i<m;i++)
   {
      cin>>a>>b>>c;
      if(Edge[a][b] > c){ //간선이 중복되게 들어오면 짧은 거리가 입력되도록
         Edge[a][b] = c;
      }
   }
}

void Floyd(){

   for(int middle=1;middle<=n;middle++)
   {
      for(int from=1;from<=n;from++)
      {
         for(int to=1;to<=n;to++)
         {
            if(Edge[from][middle]!=INF && Edge[middle][to]!=INF){
               Edge[from][to] = min(Edge[from][to], Edge[from][middle]+Edge[middle][to]);
            }
         }
      }
   }
   for(int i=1;i<=n;i++)
   {
      for(int j=1;j<=n;j++)
      {
         if(i==j || Edge[i][j]==INF)
            cout<<0<<" ";
         else
            cout<<Edge[i][j]<<" ";
      }
      cout<<"\n";
   }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Floyd();

    return 0;
}

 

후기

 최단경로 문제다. 다익스트라와 다른 점은, 다익스트라는 특정한 하나의 정점에서 다른 정점들까지의 최단거리고, 플로이 와샬은 모든 정점에서 다른 모든 정점까지의 최단거리라고 한다.

 구현은 쉬운편인데, DP와 관련있는 방법이라 그런지 살짝 직관적이지 않다.

 

풀이

(1) 간선 정보를 가진 2차원 행렬을 만든다. 먼저 INF로 초기화하고, 나중에 간선정보([출발][도착]=비용)를 입력받는다.

(2) 3개의 for문을 사용한다. 순서대로 middle, from, to 순서다. 간선[from][to]를 간선[from][middle]+간선[middle][to]와 비교하여, 더 최단거리인 것을 가져온다.