Sho1007

MMORPG 클라이언트 개발자 지망생

2 minute read

11404 플로이드 (c++)

문제

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

접근 방식

Graph, Floyd Warshall
마을(노드) 와 버스 (엣지) 가 주어진다.
자기 자신으로 가는 버스는 없고, A 마을에서 B 마을까지 가는 버스가 한개가 아닐 수 있다. (최소값 비교 필요)
각 마을에서 마을로 갈 수 있는 최단 거리를 구하라.

  1. k를 기점으로 i에서 j까지 가는 거리를 최신화하는 FW 알고리즘 사용
  2. N 은 100 이므로 O(N3)이라고 해도 1’000’000 이므로 1초 안에 해결 가능 (시간 제한)
  3. 각 엣지를 나타내는 2차원 int 배열 역시 N이 100이어도 4 * 100 * 100 = 40KB 밖에 안하므로 가능 (메모리 제한)

문제 풀이

#include <iostream>
#include <vector>
#define endl '\n'
#define INF 987654321
using namespace std;

inline int Min(int a, int b) { return a < b ? a : b; }

int N, M, a, b, c;
vector<vector<int>> v;

void Print()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            cout << v[i][j] << ' ';
        }
        cout << endl;
    }
}

void FW()
{
    for (int k = 1; k <= N; ++k)
    {
        for (int i = 1; i <= N; ++i)
        {
            for (int j = 1; j <= N; ++j)
            {
                if (i == j) continue;
                if (v[i][k] == 0 || v[k][j] == 0) continue;
                if (v[i][j] == 0) v[i][j] = v[i][k] + v[k][j];
                else v[i][j] = Min(v[i][j], v[i][k] + v[k][j]);
            }
        }
    }
}

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

    cin >> N >> M;

    v = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; ++i) v[i][i] = 0;

    while (M-- > 0)
    {
        cin >> a >> b >> c;
        if (v[a][b]) v[a][b] = Min(v[a][b], c);
        else v[a][b] = c;
    }

    FW();

    Print();

    return 0;
}

다시 생각해 볼 점

  1. 간선이 하나가 아닐 수 있다하여 최소값 비교는 잘 했었다.
  2. 하지만 98%에서 계속 틀렸었는데, 문제의 ‘도달할 수 없는 경우 0 을 출력하시오’ 라는 조건을 체크하지 못했기 때문이었다. (내가 자체적으로 명시한 INF = 987654321 을 출력하고 있었음)
  3. 처음부터 벡터를 0으로 초기화하고, 벡터에 입력받을 때와, FW 알고리즘을 수행할 때 추가 조건을 걸어주기로 했다.
    1. 초기화
      1. 기존엔 INF 로 초기화 되어있어서 v[a][b] = Min(v[a][b], c) 하면 알아서 최소값이 들어갔지만 이제는 0으로 초기화 되어있기 때문에 원하는데로 동작하지 않았다.
      2. a == b 인 간선은 없다고 했으므로, if (v[a][b] == 0) v[a][b] = c 를 해줬고,
      3. 0이 아닌 경우는 else v[a][b] = Min(v[a][b], c) 를 해줬더니 정삭 작동했다.
    2. FW
      1. 기존엔 INF로 초기화 되어있었으므로, 그냥 k, i, j로 3중 for문을 돌리면 끝났다.
      2. 하지만 이제 0이 초기화 값이므로,
        1. if (i == j) continue; 를 넣어 나 자신이 혹시나 0 이외의 값으로 초기화되는 것을 막아주고
        2. if (v[i][k] == 0   v[k][j] == 0) continue; 를 넣어 경로가 없는데 더 작은 값으로 인식되는 경우를 막았다.
        3. if (v[i][j] == 0) v[i][j] = v[i][k] + v[k][j]; 위에서 나 자신으로의 경로를 막고, 돌아가는 경로가 무한인 경우를 막았기 때문에, i에서j로 가는 경로가 무한이면 그대로 k를 경유하는 경로로 초기화 해줬다.
        4. else v[i][j] = Min(v[i][j], v[i][k] + v[k][i]); 마지막으로 경로가 존재하는 경우 현재 코스트와 k를 경유하는 코스트를 비교하여 최신화 해줬다.

You may also enjoy