[백준 / BOJ] C++ 11403 경로 찾기

11403번: 경로 찾기

 

문제

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

11403번: 경로 찾기

 

 

풀이

(i, j)의 값이 0이면 연결되어 있지 않은 것이고 1이면 i->j 연결되어 있는 것이다. 따라서 dist[i][j]에 입력을 받아 0이면 연결되어 있지 않으므로 INF로, 1이면 1을 저장해 준다. 플로이드-워셜 알고리즘으로 모든 최단거리를 구하고 i->j로 갈 수 있는 경우엔 1을, INF라면 0을 출력해 주면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, dist[101][101];
  cin >> N;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      cin >> dist[i][j];
      if (dist[i][j] == 0)
        dist[i][j] = INF;
    }
  // 플로이드 워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++)
      cout << (dist[i][j] == INF ? 0 : 1) << ' ';
    cout << '\n';
  }
  return 0;
}