[Algorithm] Baekjoon 1865번 : 웜홀

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

1865번: 웜홀

struct Node
{
    int node;
    long long distance;
};
 
long long dist[2501];
bool isInQueue[2501];
int updateCount[2501];
 
int tc, n, m, w, s, e, t;
 
 
bool SPFA(int start, vector<vector<Node>>& graph)
{
    queue<Node> q;
    q.push({ start,0 });
 
    dist[start] = 0;
    isInQueue[start] = true;
    updateCount[start] = 1;
 
    while (!q.empty())
    {
        int curNode = q.front().node;
        q.pop();
 
        isInQueue[curNode] = false;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextDistance = graph[curNode][i].distance + dist[curNode];
 
            if (nextDistance < dist[nextNode])
            {
                dist[nextNode] = nextDistance;
                updateCount[nextNode] += 1;
 
                if (isInQueue[nextNode]) continue;
 
                if (updateCount[nextNode] >= n) return false;
 
                isInQueue[nextNode] = true;
                q.push({ nextNode,nextDistance });
 
            }
        }
    }
 
    return true;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> tc;
 
    for (int i = 0; i < tc; ++i)
    {
        fill(dist, dist + 2501, 1e18);
        fill(isInQueue, isInQueue + 2501, false);
        
        vector<vector<Node>> graph(2501);
 
        bool check = false;
 
        cin >> n >> m >> w;
 
        for (int j = 0; j < m; ++j)
        {
            cin >> s >> e >> t;
 
            graph[s].push_back({ e,t });
            graph[e].push_back({ s,t });
        }
 
        for (int k = 0; k < w; ++k)
        {
            cin >> s >> e >> t;
 
            graph[s].push_back({ e,-t });
        }
 
        for (int l = 1; l <= n; ++l)
        {
            fill(updateCount, updateCount + 2501, 0);
            check = SPFA(l, graph);
 
            if (!check) break;
        }
 
        if (check) // 싸이클 없으면
        {
            printf("NO\n");
        }
        else // 싸이클 있으면.
        {
            printf("YES\n");
        }
    }
}

 

solved.ac의 class4문제를 풀던 중, 이 문제를 통해 처음으로 음수가중치를 처리하는 알고리즘을 공부해서 구현했다.

물론 타임머신이 먼저 글은 일찍 올라오긴 했는데, 그건 타임머신이 좀 더 기본예제문제같아서 먼저 풀어봤었다.

 

이 문제같은 경우는 좀 더 꼼꼼히 읽어봐야 한다.

일반 간선같은경우는 양방향이고, 음수간선은 단방향이다.

무조건 1번지점이 아니라 어디서 출발하든 다시 출발지점으로 왔을 때 시간이 역행되어 있는 상태, 즉 음수싸이클이 존재하는지만 찾으면 된다.

 

그렇기 때문에 각 테스트케이스마다 1번부터 n번까지의 노드에대해 SPFA를 실행한다. 한번이라도 음수싸이클이 있으면 더 탐지할 필요가 없기 때문에 다음 노드들을 검사할 필요는 없다.

 

테스트케이스마다 dist를 초기화해줄 경우 20ms정도고 SPFA를 수행할때마다 초기화해주면 100ms가 넘게 나온다.

난 이제 막 기본문제들 푸는 실정이라 당연히 SPFA를 수행할때마다 dist를 초기화를 시켜줘야한다고 생각했다.

뇌피셜로는 단순히 사이클이 있는지 없는지만 찾으면 되기 때문에 굳이 SPFA마다 초기화가 아니라 테스트케이스마다만 초기화 시켜주면 되는 것 같다.

즉, dist에 뭔 값들이 들어있던 아무 상관 없고, dist값들이 어떤 값들이 들어있든 음수사이클이 존재하는곳에선 n번이상의 업데이트가 발생하기 때문에 그 부분만 잘 캐치하면 되기 때문이다.