baekjoon 11404:플로이드

baekjoon 11404 플로이드

11404번 플로이드

접근

플로이드 워셜 알고리즘 쓰는 문제이다.
원래는 3차원으로 만드는 거지만 2차원으로 해도 문제없다.
코드에서 더 자세히 설명하겠다.

코드

#include <iostream>
#include <vector>
#define INF 100000000
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int n, m;
  cin >> n;
  cin >> m;
  vector<vector<int>> d(n, vector<int>(n, INF));
  for(int i = 0; i < n; i++){
    d[i][i] = 0;
  }
  
  while(m--){
    int a, b, w;
    cin >> a >> b >> w;
    if(d[a-1][b-1] > w){ //초기세팅: 중간에 아무런 node 없는경우
      d[a-1][b-1] = w;
    }
  }

  for(int k = 0; k < n; k++){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        //중간에 0 node 갔다오는경우
        //중간에 0~1 node 갔다오는 경우
        //중간에 0~n-1 node 갔다오는 경우
        //k=5일때의 loop는 0~5 node를 갔다오는 경우이고 d^5[i][j] = min(d^4[i][j], d^4[i][5]+d^4[5][j])이다. 
        //d^4[i][j]야 자명한데(아직 업데이트 안했으니까), d^4[i][5], d^4[5][j]인지는 사실 d^5[i][5] == d^4[i][5], d^5[5][j] == d^4[5][j]이므로 
        //먼저 업데이트 된 상태여도 아니여도 상관없다.
      }
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(d[i][j] == INF) d[i][j] = 0;
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cout << d[i][j] << ' ';
    }
    cout << '\n';
  }
  
  return 0;
}

배운 점

플로이드 워셜 알고리즘 직접구현 해봤다.
플로이드 워셜 알고리즘은 음의 간선은 있어도 된다.
하지만 음의 사이클은 있으면 안된다.