BOJ 1865 : 웜홀 [C++]

문제

 

최단거리 문제인데도 파블로프의 개마냥 dfs 조졌다가 실패하고,

문제 카테고리를 보고 알았다.

물론 벨만 포드라고 적혀있는걸 보고는 '벨만 포드라고?'라고 생각했는데,

바로 아차싶었다.

소요시간 중에 음수가 있기 때문에 최단 거리를 찾으면 되는 거라고 생각했다.

이전 문제와 같이 벨만 포드가 기억이 안나 구글링하여 코드를 작성했는데,

94%에서 시간 초과가 떠서 한 시간 정도 고민하다 결국 gg치고 질문 검색 탭을 찾아갔다.

 

 

이 글을 보고도 처음에는 무슨 말인가 이해가 되지않아서 정답 코드와 해설이 있는 블로그를 구글링했는데,

이 분의 해설을 보고 문제의 함정과 왜 코드를 저렇게 썼는지 이해할 수 있었다.

 

벨만 포드에서는 소요 시간이 음수인 엣지를 사이클 마냥 도는 경우가 있는지를 찾는데,

문제에 갔던 곳을 다시 방문하지 않는다는 말이 없기 때문에 이런 경우를 허용한다고 이해했다.

소요 시간이 음수인 엣지와 사이클을 이루어 계속 돈다면, 어찌됐건 총 소요 시간은 음수가 될 것이고,

출발지점으로 돌아오기만 하면 출력 YES의 조건을 만족하게 된다.

그래서 백준 질문 검색 탭의 글에서도 음수 사이클이 있기만 하면 YES를 출력하는 것에 대해 얘기했던 것이다.

 

#include <iostream>
#include <vector>

void bellman(int vertex, int dist[], std::vector<std::pair<int, int>> edges[]) {
    for (int i = 1; i < vertex + 1; i++) {
        for (int j = 1; j < vertex + 1; j++) {
            for (auto p: edges[j]) {
                int cur_vertex = j;
                int next_vertex = p.first;
                if (dist[cur_vertex] + p.second < dist[next_vertex]) {
                    dist[next_vertex] = dist[cur_vertex] + p.second;
                }
            }
        }
    }
    for (int i = 1; i < vertex + 1; i++) {
        for (auto p: edges[i]) {
            int cur_vertex = i;
            int next_vertex = p.first;
            if (dist[cur_vertex] + p.second < dist[next_vertex]) {
                std::cout << "YES\n";
                return;
            }
        }
    }
    std::cout << "NO\n";
    return;
}

int main() {
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    std::ios::sync_with_stdio(false);

    int tc = 0;
    std::cin >> tc;

    for (int i = 0; i < tc; i++) {
        std::vector<std::pair<int, int>> edges[501];
        int vertex = 0, edge = 0, hole = 0;
        std::cin >> vertex >> edge >> hole;
        for (int j = 0; j < edge; j++) {
            int start = 0, end = 0, spend = 0;
            std::cin >> start >> end >> spend;
            edges[start].push_back({end, spend});
            edges[end].push_back({start, spend});
        }
        for (int j = 0; j < hole; j++) {
            int start = 0, end = 0, spend = 0;
            std::cin >> start >> end >> spend;
            edges[start].push_back({end, -spend});
        }
        int dist[501];
        bellman(vertex, dist, edges);
    }
    return 0;
}

 

이해하고 나니 허탈하긴 했지만,

문제를 읽고 제대로 이해하지 못했다는 점, 벨만 포드를 몰라 구글링한 점에서

뭐가 부족한지 알 수 있었다.