[백준][C++]11404번 플로이드

문제

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

11404번: 플로이드

 

 

풀이

• 시작 도시 A와 도착 도시 B를 연결하는 간선이 여러 개일 수 있다.

⇒ 초기에 간선 정보를 입력받을 때 '가장 짧은 간선' 정보만 저장한 뒤에, 플로이드 워셜 알고리즘을 수행하여 결과를 출력한다.

 

• 만약 정답 배열의 값이 최초 초기화한 충분한 큰 수일 때는 도착할 수 없는 경로이기 때문에 0을 출력, 아니면 배열의 값을 출력한다.

 

플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

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

  int n, m;
  cin >> n >> m;  // 노드의 개수 및 간선의 개수를 입력받기

  // 인접 행렬 초기화
  vector<vector<int>> cost(n + 1, vector<int> (n + 1, 10000000));  // 충분히 큰 수로 저장
  for(int i = 1; i <= n; i++)
  {
    cost[i][i] = 0;  // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
  }
  
  for(int i = 0; i < m; i++)
  {
    int a, b, c;
    cin >> a >> b >> c;

    cost[a][b] = min(cost[a][b], c);  // 노선 데이터를 cost 행렬에 저장하기
  }

  // 플로이드 워셜 알고리즘 수행
  for(int k = 1; k <= n; k++)
  {
    for(int i = 1; i <= n; i++)
    {
      for(int j = 1; j <= n; j++)
      {
        cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
      }
    }
  }

  // 정답 배열 출력하기
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= n; j++)
    {
      // 도달할 수 없는 경우, 0을 출력
      if(cost[i][j] == 10000000)
      {
        cout << "0 ";
      }
      // 도달할 수 있는 경우 거리를 출력
      else
      {
        cout << cost[i][j] << " ";
      }
    }
    cout << "\n";
  }

  return 0;
}

 

 

오답

#include <iostream>

using namespace std;

static int N, M;
static long mdistance[101][101];

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

  cin >> N >> M;

  // 인접 행렬 초기화
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= N; j++)
    {
      if(i == j)
      {
        mdistance[i][j] = 0;
      }
      else
      {
        mdistance[i][j] = 10000001;  // 충분히 큰 수로 저장
      }
    }
  }
  
  for(int i = 0; i < M; i++)
  {
    int s, e, v;
    cin >> s >> e >> v;
    if(mdistance[s][e] > v)
    {
      mdistance[s][e] = v;
    }
  }
  
  // 플로이드 워셜 알고리즘 수행
  for(int k = 1; k <= N; k++)
  {
    for(int i = 1; i <= N; i++)
    {
      for(int j = 1; j <= N; j++)
      {
        if(mdistance[i][j] > mdistance[i][k] + mdistance[k][j])
        {
          mdistance[i][j] = mdistance[i][k] + mdistance[k][j];
        }
      }
    }
  }
  
  for(int i = 1; i <= N; i++)
  {
    for(int j = 1; j <= N; j++)
    {
      if(mdistance[i][j] == 10000001)
      {
        cout << "0 ";
      }
      else
      {
        cout << mdistance[i][j] << " ";
      }
    }
    cout << "\n";
  }
}