[백준 C++] 11404번 - 플로이드

문제 소개

 

11404번: 플로이드

 n(2 ≤ n ≤ 100) 개의 도시가 존재하고, 어느 도시 A에서 출발하여 B로 가는 m(1 ≤ m ≤ 100,000) 개의 버스가 존재한다. 또한 각 버스에는 한 번 사용할 때 필요한 비용이 있다.

 

 모든 도시의 쌍에 대하여 도시 A에서 B로 가는데 필요한 비용의 최솟값을 출력하라.

---

문제 풀이 전략

 

기획

 

플로이드-워셜 알고리즘 - 나무위키

 가장 먼저 생각난 전략은 각 노드 사이의 간선 가중치에 대한 정보를 담은 n x n 크기의 배열을 만든 다음에, 계속해서 노드 간 최단 거리를 갱신해 나가는 방법으로 문제를 해결하려고 했다. 다시말해, 플로이드-워셜 알고리즘으로 문제를 해결하고자 했다.

 

 이 방법은 고전적인 방향 그래프의 각 노드 사이의 최단 거리를 구하는 방식으로써, 위에서 만든 배열을 a번 제곱한 후(정확히는 제곱의 과정에서 더해지는 요소의 최솟값으로 갱신하는 과정의 a번 반복)의 배열의 어떤 원소 (i, j)에 담긴 값의 의미는, i에서 j까지 a번 이하로 간선을 이동하였을 때 걸리는 최단거리를 말한다. 따라서 충분히 큰 크기의 a로 배열을 제곱하고 난다면, 문제를 풀 수 있을 것이라 판단했다.

 

 이 문제의 경우, 아무리 최악의 경우라도 노드의 개수가 최대 100개이기 때문에, 100번 이하의 간선 이동 끝에 최단 거리로 어떤 노드 i, j를 연결할 수 있을 것이다. 따라서 배열을 총 7번 제곱한다면(2^7 == 128), 충분히 최단 거리를 구할 수 있을 만큼 큰 크기라 판단하였다.

---

설계

 

 이 문제를 풀기 위해서, 다음의 4가지 함수를 만들고 사용할 것이다.

1. 입력을 받는 scanData() 함수
2. 배열을 제곱하는 arrSquare() 함수
3. 배열을 7번 제곱하는 solveProblem() 함수
4. 정답을 출력하는 printAnswer() 함수

 또 위의 Matrix Multiplication Algorithm을 이용하기 위해서 무한에 대한 정의를 내려야 하는데, 간선의 가중치는 최대 100000이고 노드는 최대 100개이므로 100000 x 100 + 1 = 10000001 이상의 수를 무한이라 정의하면, 충분하리라 판단하였다.

---

주의 사항

 

 무한의 크기를 충분히 크게 했는지, 갈 수 없는 경우에 0을 출력했는지 유의해야 한다.

---

소스 코드

 

#include <iostream>
using namespace std;

void scanData();
void arrSquare();
void solveProblem();
void printAnswer();

const int INFI = 100000000;
int n, m;
int arr[100][100];
int newArr[100][100];

int main()
{
    scanData();
    solveProblem();
    printAnswer();

    return 0;
}

void scanData()
{
    scanf("%d", &n);
    scanf("%d", &m);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            arr[i][j] = INFI;

    for(int i = 0; i < n; i++)
        arr[i][i] = 0;

    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        if(arr[a-1][b-1] > c)
            arr[a-1][b-1] = c;
    }
}

void arrSquare()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            newArr[i][j] = 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            newArr[i][j] = arr[i][j];

            for(int x = 0; x < n; x++)
                if(arr[i][x] != INFI && arr[x][j] != INFI && newArr[i][j] > arr[i][x] + arr[x][j])
                    newArr[i][j] = arr[i][x] + arr[x][j];
        }
    }

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            arr[i][j] = newArr[i][j];
}

void solveProblem()
{
    for(int i = 0; i < 7; i++)
        arrSquare();
}

void printAnswer()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(arr[i][j] != INFI)
                printf("%d", arr[i][j]);
            else
                printf("0");

            if(j != n - 1)
                printf(" ");
        }
        printf("\n");
    }
}

---

테스트 케이스

 

[예제 1]
입력:
5
5
1 2 1
2 3 1
3 1 1
4 5 1
5 4 1

출력:
0 1 2 0 0
2 0 1 0 0
1 2 0 0 0
0 0 0 0 1
0 0 0 1 0

[예제 2]
입력:
2
1
1 2 1

출력:
0 1
0 0

[예제 3]
입력:
5
3
1 2 5
1 2 3
1 2 1

출력:
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

[예제 4]
입력:
15
14
1 2 100000
2 3 100000
3 4 100000
4 5 100000
5 6 100000
6 7 100000
7 8 100000
8 9 100000
9 10 100000
10 11 100000
11 12 100000
12 13 100000
13 14 100000
14 15 100000

출력:
0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 1100000 1200000 1300000 1400000
0 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 1100000 1200000 1300000
0 0 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 1100000 1200000
0 0 0 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 1100000
0 0 0 0 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000
0 0 0 0 0 0 100000 200000 300000 400000 500000 600000 700000 800000 900000
0 0 0 0 0 0 0 100000 200000 300000 400000 500000 600000 700000 800000
0 0 0 0 0 0 0 0 100000 200000 300000 400000 500000 600000 700000
0 0 0 0 0 0 0 0 0 100000 200000 300000 400000 500000 600000
0 0 0 0 0 0 0 0 0 0 100000 200000 300000 400000 500000
0 0 0 0 0 0 0 0 0 0 0 100000 200000 300000 400000
0 0 0 0 0 0 0 0 0 0 0 0 100000 200000 300000
0 0 0 0 0 0 0 0 0 0 0 0 0 100000 200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0