본문 바로가기
알고리즘!/Graph

[C/C++] 백준 11404: 플로이드 (플로이드-워셜 알고리즘)

by soeayun 2023. 9. 11.

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

 

11404번: 플로이드

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가

www.acmicpc.net

 

플로이드-워셜 알고리즘?

 

 알고리즘 제목에서도 알 수 있다싶이 이 문제는 한 도시에서 다른 도시까지 필요한 비용의 최솟값을 구하는 알고리즘 문제이기 때문에 그래프에서 한 지점에서 다른 지점까지의 최솟값을 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 된다.

 

 특징으로는 다익스트라 알고리즘에 비해 구현이 쉽고 삼중 반복문을 사용하기 때문에 O(V^3)의 시간 복잡도를 갖는다. 삼중 반복문을 돌때 가장 바같쪽에 있는 for문의 변수가 중간 지점(경유하는 애)여야 한다!!! 이 알고리즘의 작동 방식은 아래 블로그에서 잘 설명되어 있어 참고하면 좋을 듯 하다.

 

http://dongdd.tistory.com/107

 

Floyd-Warshall(플로이드 와샬) 알고리즘

Floyd-Warshall(플로이드 와샬) 알고리즘 Floyd-Warshall Algorithm - 그래프에서 모든 정점 사이의 최단 거리를 구하기 위한 알고리즘- 다익스트라 알고리즘을 모든 정점에서 수행한 것과 같은 알고리즘이

dongdd.tistory.com

 

 

 

 

구현 특징!

 

 가장 큰 특징으로는 배열의 초기값을 10,000,000으로 잡은 것이다. 초기값을 -1로 잡고 해도 되지만 이렇게 할 경우 반복문에서 따로 -1인 것을 확인해줘야하므로 코드가 복잡해질 수도 있다. 초기값을 10,000,000으로 잡은 이유는 한 도시에서 다른 도시까지의 최대비용이 100,000이고 한 도시에서 다른 도시까지 거쳐가는 가장 큰 경우의 수는 98개 도시를 거쳐가는 것이므로 넉넉잡아 100*100,000의 계산값으로 나온 것이다. 이렇게 할 경우에!

 

graph[i][k]=min(graph[i][k],graph[i][j]+graph[j][k]);

 

만으로 삼중 for문을 구현 가능하기 때문이다!

 

 이렇게 할 경우 맨 마지막에 그래프를 한 번 돌면서 값이 10,000,000이라면 도시에서 도시로 갈 수 없는 경우의 수이므로 0으로 바꿔주었고 이렇게 하는 것이 비효율적이지 않는 이유는 이미 플로이드 알고리즘을 돌면서 O(V^3)만큼의 시간복잡도를 썼기 때문에 이를 확인하는 이중for문은 O(V^2)밖에 걸리지 않아 무시할만 하다.

 

 한 가지 주의해야할 점은 a도시에서 a도시로의 필요한 비용의 최솟값은 0이므로 (1->4: 10, 4->1: 5 라고 해도 1->1에 필요한 최솟값은 15가 아닌 0이다) 출발지와 도착지가 같을 때는 continue를 써줬다.

 

소스코드

#include <iostream>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<map>
#include<set>
using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

int graph[101][101];

void clear()  //엄청 큰 값으로 초기화
{
 for(int i=0;i<=101;i++)
   {
     for(int j=0;j<=101;j++)
       {
         graph[i][j]=10000000;
       }
   }
}


int main() {    
  int city,bus;
  cin>>city>>bus;
  clear();
  for(int i=1;i<=bus;i++)
    {
      int tmp1,tmp2,price;
      cin>>tmp1>>tmp2>>price;      
      graph[tmp1][tmp2]=min(graph[tmp1][tmp2],price);
    }

  for(int j=1;j<=city;j++)
    {
      for(int i=1;i<=city;i++)
        {
          for(int k=1;k<=city;k++)
            {
              if(k==i) //a도시에서 a도시로의 비용은 0임
                continue;
              graph[i][k]=min(graph[i][k],graph[i][j]+graph[j][k]);
            }
        }
    }
  

  for(int j=1;j<=city;j++)
    {
      for(int i=1;i<=city;i++)
        {
          if(graph[j][i]==10000000) //한번도 방문하지 않은 곳
            graph[j][i]=0;
          cout<<graph[j][i]<<" ";
        }
      cout<<"\n";
    }
  
}