Beakjoon] 플로이드(백준 11404 코테) - 그래프 (C++) (플로이드-워셜)

---

🅰️문제주소 : https://www.acmicpc.net/problem/11404

 

🚩문제 

 

 

🪡풀이 

 - 그래프에서 최단거리를 구할때는 플로이드-워셜 알고리즘을 사용한다
 - 시간복잡도가 O(V^3)이므로 노드 개수를 확인하여 해당 알고리즘을 요구하는 문제가 맞는지 확인해본다
 - 충분히 큰 수로 초기화 할 때 MAX값을 사용하지 않도록 주의한다 (별도로 MAX값을 체크하지 않으면 중간 경로 거리 합산을 구할 때 최대값을 초과하여 음수가 되어버릴 수 있다)
 - 노드의 개수가 정해져있고 크지 않으므로 굳이 vector보다는 이차원배열이 속도가 빠르다

 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int N, M;
    vector<vector<int64_t>> map;

    cin >> N;
    cin >> M;

    map.resize(N+1, vector<int64_t>(N+1));

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = 10000001;
        }
    }

    for (int i = 0; i < M; ++i)
    {
        int start, end, cost;
        cin >> start >> end >> cost;
        if(map[start][end] > cost)
            map[start][end] = cost;
    }

    for (int k = 1; k <= N; ++k)
    {
        for (int i = 1; i <= N; ++i)
        {
            for (int j = 1; j <= N; ++j)
            {
                if(map[i][j] > map[i][k] + map[k][j])
                    map[i][j] = map[i][k] + map[k][j];
            }
        }
    }

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            if (map[i][j] == 10000001)
                cout << "0";
            else
                cout << map[i][j];

            if (N != j)
                cout << " ";

        }
        if (N != i)            
            cout << "\n";
    }

    return 0;
}

 

💡알게 된 것 

 - 플로이드-워셜 알고리즘
 - 초기화시 최대값이 아닌 충분히 큰 값으로 최초기화 하기
 - 백준에서 출력초과시 단순 출력 문제가 아니라 주로 답을 틀렸기에 출력내용을 초과할 가능성이 높다
 - 다른 그래프 문제와 동일하게 인덱스 1번부터 써야 편하다

---