백준 11404번 플로이드 문제 풀기

문제 설명

• 모든 도시 A에서 B로 가는데 필요한 비용의 최솟값 구하기
• 도시의 개수 n(2 ≤ n ≤ 100)
• 노선의 개수 m(1 ≤ m ≤ 100,000)
• 비용은 100,000보다 작거나 같은 자연수

문제를 보고 든 생각

• n:n의 최단 경로를 구해야한다.
• 도시의 개수가 100개 밖에 되지 않는다.
• 플로이드 와샬 알고리즘으로 풀어야겠다.

간단한 풀이 설명

1. n:n의 최단 경로는 웬만하면 플로이드 와샬로 풀린다.
2. 플로이드 와샬을 사용하기 위해 인접 행렬(G)을 사용했다.
3. 플로이드 와샬을 이해하기는 어렵다. 다만 코드를 외우기는 쉽다.
4. i에서 j로 가는데 k를 거치는 모든 경우를 보면 된다.

코드

#include <iostream>

#define MAX_N 101
#define MAX_W 2147483647

using namespace std;

int N, M;
long long G[MAX_N][MAX_N];

void initG(int n){
  for(int i=1; i<=n; ++i){
    for(int j=1; j<=n; ++j){
      if(i == j){
        G[i][j] = 0;
        continue;
      }
      G[i][j] = MAX_W;
    }
  }
}

void floyd(int n){
  for(int k=1; k <= n; ++k){
    for(int i=1; i <= n; ++i){
      for(int j=1; j <= n; ++j){
        if(G[i][k] + G[k][j] < G[i][j]){
          G[i][j] = G[i][k] + G[k][j];
        }
      }
    }
  }
}

void printG(int n){
  for(int i=1; i<=n; ++i){
    for(int j=1; j<=n; ++j){
      if(G[i][j] == 2147483647){
        cout << 0 << " ";
      } else {
        cout << G[i][j] << " ";
      }
    }cout << "\n";
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> N >> M;
  initG(N);
  for(int i=0; i<M; ++i){
    int a, b, w; cin >> a >> b >> w;
    if(G[a][b] > w){
      G[a][b] = w;
    }
  }
  floyd(N);
  printG(N);

  return 0;
}