백준 Gold 3 웜홀

웜홀 (백준 Gold 3)

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

주어지는 간선 정보를 통하여
음수 사이클이 존재하는지 찾는 문제

• 도로는 양방향 이나,
  웜홀은 단방향
  

• 시작점 / 끝점의 간선 중복 가능
  

풀이 방법

음수 사이클을 찾는 문제이기에
벨만-포드를 적용함으로서 풀 수 있다고 생각하였다

벨만-포드

• 임의의 시작점을 하나 잡은 후
  해당 시작점에서의 ‘거리’를 0으로 잡는다
  (나머지는 매우 높은 값)
  

• 각 정점의 개수만큼
  이후 주어진 간선을 돌면서
  간선 목적지 비용 > 간선 시작 비용 + 간선 비용
  이라면 간선 목적지 비용을 갱신
  

• 모든 간선을 돈 후
  마지막으로 ‘간선’만 한 번 순회하여
  간선 목적지 비용 > 간선 시작 비용 + 간선 비용이
  ‘갱신’된다면 음수 사이클이 존재함으로 판단
  

첫 제출 코드

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<limits.h>

using namespace std;

bool belmanFord(int n, unordered_map<int, unordered_map<int, int>>& umaps, int start)
{
	vector<int> dist(n, INT_MAX);
	dist[start] = 0;

	for (int i = 0; i < n; i++)
	{
		for (auto& p1 : umaps)
		{
			int s = p1.first;
			for (auto& p2 : p1.second)
			{
				int t = p2.first;
				int cost = p2.second;

				if (dist[s] != INT_MAX &&
					dist[t] > dist[s] + cost)
				{
					dist[t] = dist[s] + cost;
				}
			}
			
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (auto& p1 : umaps)
		{
			int s = p1.first;
			for (auto& p2 : p1.second)
			{
				int t = p2.first;
				int cost = p2.second;

				if (dist[s] != INT_MAX &&
					dist[t] > dist[s] + cost)
				{
					return true;
				}
			}
			
		}
	}

	return false;
}

int main()
{
	int t;
	cin >> t;
	while (t)
	{
		int n, m, w;
		cin >> n >> m >> w;
		unordered_map<int, unordered_map<int, int>> umaps;

		for (int i = 0; i < m; i++)
		{
			int s, e, t;
			cin >> s >> e >> t;
			s--;
			e--;
			if (umaps[s].find(e) == umaps[s].end())
				umaps[s][e] = t;
			else if (umaps[s][e] > t)
				umaps[s][e] = t;

			if (umaps[e].find(s) == umaps[e].end())
				umaps[e][s] = t;
			else if (umaps[e][s] > t)
				umaps[e][s] = t;
		}

		for (int i = 0; i < w; i++)
		{
			int s, e, t;
			cin >> s >> e >> t;
			s--;
			e--;
			umaps[s][e] = -t;
		}

		bool bCycle = false;

		for (int i = 0; i < n; i++)
		{
			if (belmanFord(n, umaps, i))
			{
				bCycle = true;
				break;
			}
		}

		if (bCycle)
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';

		t--;
	}

	return 0;
}

틀린 이유?

개인적으로는 ‘음수 사이클’만 검사하므로
괜한 추가적으로 주어지는 중복 간선은 필요 없다고 생각하여
처음에 중복 간선을 쳐내는 방식을 사용하였으나

그럼에도 시간초과가 발생하였다

따라서 로직을 수정할 필요가 있다고 생각하였다

• 현재는 벨만-포드를 n번 순회
  

• 또한 벨만-포드 마지막에 n번 순회
  

최종 제출 코드

#include<iostream>
#include<vector>
#include<string>
#include<limits.h>

using namespace std;

struct edge
{
	int s, t, cost;
};

bool belmanFord(int n, vector<edge>& edges)
{
	vector<int> dist(n, 0);

	for (int i = 0; i < n; i++)
	{
		for (edge& e : edges)
		{
			int s = e.s;
			int t = e.t;
			int cost = e.cost;

			if (dist[t] > dist[s] + cost)
			{
				dist[t] = dist[s] + cost;
			}
		}
	}

	for (edge& e : edges)
	{
		int s = e.s;
		int t = e.t;
		int cost = e.cost;

		if (dist[t] > dist[s] + cost)
		{
			return true;
		}
	}

	return false;
}

int main()
{
	int t;
	cin >> t;
	while (t)
	{
		int n, m, w;
		cin >> n >> m >> w;
		vector<edge> edges;

		for (int i = 0; i < m; i++)
		{
			int s, e, t;
			cin >> s >> e >> t;
			s--;
			e--;
			edges.push_back({ s,e,t });
			edges.push_back({ e,s,t });
		}

		for (int i = 0; i < w; i++)
		{
			int s, e, t;
			cin >> s >> e >> t;
			s--;
			e--;
			edges.push_back({ s,e,-t });
		}

		if (belmanFord(n, edges))
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';

		t--;
	}

	return 0;
}

수정 방향

• 임의의 시작점을 잡는다고 가정하기에 전부 0으로 초기화
  (Super Source : 가상의 시작점)
  n번 사이클을 한번 돌리면서
  음수 값을 ‘적용’함
  
  • 이를 통해 음수값 Dist가 n번 반복하면서
    최단 거리를 갱신함
    
  • 어차피 죄다 0인데 그냥 이 과정 필요 없지 않나?
    
    • 우리가 원하는 것은 Cycle 체크임
      이 과정이 없다면 값이 틀릴 수 있음
      (음수값이 충분히 퍼지지 않아, 사이클 체크가 안될 수 있다!)
      
• 이렇게 구해진 ‘최단 거리’에서
  다시 edge 루프를 돌려 ‘갱신’된다면
  음수 사이클이 확정됨
  

결과

단순한 벨만-포드 문제인 줄 알았으나..
생각보다 매우 까다로운 문제였다

여러 검색을 통하여
‘음수 사이클’이 존재하는지만을 파악하는 로직을
구현하여 문제를 풀 수 있었던 것 같다