[백준] 11404_플로이드 C++

11 Jun 2023 in Study on Coding Test

플로이드-워셜 알고리즘의 기초를 다뤄보는 문제

정답제출코드

#include <iostream>
#include <vector>

#define INF 999999999

using namespace std;

int CityCost[101][101];

int m_min(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}

int main()
{
    int N, M;
    cin >> N;
    cin >> M;

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
            CityCost[i][j] = INF;
    }

    for (int i = 0; i < M; ++i)
    {
        int S, E, C;
        cin >> S >> E >> C;

        if (CityCost[S][E] > C)
            CityCost[S][E] = C;
    }

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            for (int k = 1; k <= N; ++k)
            {
                if (CityCost[j][i] != INF && CityCost[i][k] != INF)
                    CityCost[j][k] = m_min(CityCost[j][k], CityCost[j][i] + CityCost[i][k]);
            }
        }
    }

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            if (i == j || CityCost[i][j] == INF)
                cout << '0' << ' ';
            else
                cout << CityCost[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

사실 이번 문제는 다익스트라로 풀어도 될 것 같긴 했다.

하지만 제목이 “플로이드”, 즉 플로이드-워셜 알고리즘으로 풀라고 외치고있어서

플로이드-워셜 알고리즘에 대한 기초도 다질겸 풀었다.

플로이드-워셜 알고리즘이 사용된 구간은 아래 구간이다.

for (int i = 1; i <= N; ++i) // 거쳐가는 도시
{
    for (int j = 1; j <= N; ++j) // 출발 도시
    {
        for (int k = 1; k <= N; ++k) // 도착 도시
        {
            if (CityCost[j][i] != INF && CityCost[i][k] != INF)
                CityCost[j][k] = m_min(CityCost[j][k], CityCost[j][i] + CityCost[i][k]);
        }
    }
}

플로이드 워셜 알고리즘은 다익스트라 알고리즘에 비해서는 시간복잡도 측면상으로 불리하다.

• 플로이드-워셜 알고리즘 : O(V^3)
• 다익스트라 알고리즘 : O(N^2) (인접행렬 사용할 시) / O(NlogN) (인접 리스트 사용할 시)

하지만 가중치가 음수인 구간이 있을 때에는 반드시 플로이드-워셜 알고리즘을 사용해야한다.