백준 11403 (C++) 경로 찾기

 

아이디어

인접행렬 adj에 입력 받을 때,

갈 수 없는 경로를 0의 값을 INF (아주 큰 값)으로 바꿔 저장하고

플로이드 와샬로 adj를 탐색하면서

다른 노드를 통해 거쳐갈 수 있는 빠른 길이 있다면 갱신해주었다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int INF = 1e8;
const int MAX = 101;
int n, ans=0;
int adj[MAX][MAX];
void fw() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (adj[i][j] >= INF) {
                cout << "0 ";
            }
            else cout << "1 ";
        }
        cout << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> adj[i][j];
            if (adj[i][j] == 0) {
                adj[i][j] = INF;
            }
        }
    }
    fw();
    return 0;
}

 

 

다른 플로이드 와샬 응용 문제를 풀고싶다면 여기로

 

https://synodic.tistory.com/entry/%EB%B0%B1%EC%A4%80-14938-C-%EC%84%9C%EA%B0%95%EA%B7%B8%EB%9D%BC%EC%9A%B4%EB%93%9C

백준 14938 (C++) 서강그라운드

 

한 달 전엔 fw가 기억이 안났나 못 풀었는데

다르게 짜서 다시 제출해보니 한번에 AC 받아서 기쁘다