백준 [11657] 타임머신

 

 

음수 사이클이 있는 벨만 포드 알고리즘 문제

 

음수 사이클 탐지 구현 다 해놓고 예제도 다 맞았는데 자꾸 틀려서 뭔가 했는데

이분이 올린 테스크 케이스들 보고 알았다.

www.acmicpc.net/board/view/39180

 

틀린 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 0x7FFFFFFF

vector<pair<int, int>> v[512];
long long upper[512];

int Bellman(int N)
{
	int i, size, there, thereCost;
	upper[1] = 0;
	for (i = 1; i <= N; i++)
	{
		for (int here = 1; here <= N; here++)
		{
			size = v[here].size();
			for (int j = 0; j < size; j++)
			{
				there = v[here][j].first;
				thereCost = v[here][j].second;
				if (upper[there] > upper[here] + thereCost)
				{
					upper[there] = upper[here] + thereCost;
					// 마지막 탐색임에도 수정할 값이 있다는 것은 음수 사이클
					if (i == N)
						return 1;
				}

			}
		}
	}
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M;
	int A, B, C;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> A >> B >> C;
		v[A].push_back({ B, C });
	}
	for (int i = 0; i <= N; i++)
		upper[i] = INF;
	if (Bellman(N))
		cout << "-1\n";
	else
	{
		for (int i = 2; i <= N; i++)
		{
			if (upper[i] == INF)
				cout << "-1\n";
			else
				cout << upper[i] << '\n';
		}
	}
	return 0;
}

 

위 코드의 문제는 24번째 줄 조건문이다.

얼핏 볼 땐 문제가 없어보이지만, 비연결 그래프일 때 문제가 발생한다.

위 코드의 반례가 되는 비연결 그래프

문제에서는 1번 도시에서 출발한다고 했지만,

다음 그래프에선 3, 4번 정점은 방문할 수 없다.

그렇기 때문에, 최종 출력은 1, -1 -1 이 돼야 한다.

 

위 코드에선 별다른 조건 없이, 1부터 N까지 탐색을 하게 된다.

이렇게 되면 3, 4번끼리 서로 음수 사이클을 형성하고

28번 줄의 i==N의 조건에 걸려 출력 결과는 -1이 뜨게 된다.

 

이를 해결하는 방법은 간단하다.

방문한 적이 없는 정점이라면 그냥 건너뛰면 된다!

 

정답 코드의 28번 라인을 보면 알 수 있다.

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 0x7FFFFFFF

vector<pair<int, int>> v[512];
long long upper[512];

int Bellman(int N)
{
	int i, size, there, thereCost;
	upper[1] = 0;
	for (i = 1; i <= N; i++)
	{
		for (int here = 1; here <= N; here++)
		{
			size = v[here].size();
			for (int j = 0; j < size; j++)
			{
				there = v[here][j].first;
				thereCost = v[here][j].second;
				if (upper[here] != INF && upper[there] > upper[here] + thereCost)
				{
					upper[there] = upper[here] + thereCost;
					// 마지막 탐색임에도 수정할 값이 있다는 것은 음수 사이클
					if (i == N)
						return 1;
				}

			}
		}
	}
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M;
	int A, B, C;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> A >> B >> C;
		v[A].push_back({ B, C });
	}
	for (int i = 0; i <= N; i++)
		upper[i] = INF;
	if (Bellman(N))
		cout << "-1\n";
	else
	{
		for (int i = 2; i <= N; i++)
		{
			if (upper[i] == INF)
				cout << "-1\n";
			else
				cout << upper[i] << '\n';
		}
	}
	return 0;
}