[C++]백준(BOJ) - 11403 경로 찾기(플로이드-와샬)

 

난이도 : 실I

알고리즘 유형 : 플로이드-와샬

풀이 방법 : 3중 for문

 

문제 링크

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

 

 

이 문제는 플로이드-와샬의 기본 문제이며, 입력에 인접 행렬이 주어지고 최단경로는 구하는 문제입니다.

그리고 N이 100이 최대라는 점에서 인접 행렬 + 최단경로 = 플로이드 라는 것을 알 수 있습니다.

 

플로이드는 3중 for문으로 만들었으며 주의 사항은 최단경로이기 때문에 경로가 없는 지점은 0이 아닌 최대값을 넣어야합니다. 저같은 경우는 0x3f3f3f3f + 0x3f3f3f3f 가 overflow가 발생하지 않도록 최대값을 넣어주었습니다. 

 

#include <bits/stdc++.h>

using namespace std;

int n;
const int inf = 0x3f3f3f3f;

int board[101][101];

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

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> board[i][j];
            
            if(!board[i][j])
                board[i][j] = inf;
        }
            
    }

    
    for(int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if(board[i][j] > board[i][k] + board[k][j])
                    board[i][j] = board[i][k] + board[k][j];

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cout << (board[i][j] != inf) << ' ' ;
        }

        cout << '\n';
    }
}