11403. 경로찾기

 

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

11403번: 경로 찾기

 

해당 문제를 플로이드 와샬 알고리즘을 참고하여 풀었습니다. 

 

플로이드 와샬 알고리즘은 특정 정점으로 가는 최단 경로를 구하는 알고리즘입니다.

 

i, j로 된 그래프가 있다면 i-> j가는 경로를 구할 때 특정 노드 k를 비교해서 i->k와 k->j로 가는 경로의 합 값이 기존 i -> j 경로의 합보다 작으면 그 값으로 갱신시켜 놓습니다. 

 

문제에선 연결된 것만 알려주기 때문에 i->k, k->j로 가는 경로가 서로 연결이 되어 있다면 i->j로 가는 경로로 갱신시켜주었습니다. 

 

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;
int arr[101][101]; 

int main()
{
    int n; 

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int num; 
            cin >> num; 
            arr[i][j] = num; 
        }
    }

    // k =  거쳐가는 노드 
    for (int k = 0; k < n; k++)
    {
        // i 는 출발 노드
        for (int i = 0; i < n; i++)
        {
            // j = 도착 노드 
            for (int j = 0; j < n; j++)
            {
                // i->k k->j 가는게 i -> j로 가는 것보다 더 적니?
                if (arr[i][k] && arr[k][j] )
                {
                    arr[i][j] =1; // 해당 값 갱신 
                }
            }
        }
    }

    // 결과 출력
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << '\n';
    }




    return 0; 
}