백준 1738 - 골목길

hvv_an 2025. 7. 7. 11:17

문제 설명

민승이는 놀러가기 위해 집을 나섰다. 민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.

그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다. 그런가하면, 어떤 길에는 지나가던 행인들이 흘리고 간 금품들이 떨어져 있어, 그 길을 지나게 되면 일정한 양의 금품을 획득하게 된다. 한 번 지나간 길을 다시 방문하더라도 금품을 갈취당하거나 획득한다.

골목길의 연결 상태와, 각 골목길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이 주어졌을 때, 민승이가 최대한 유리한 경로를 따라 집에서 코레스코 콘도까지 가기 위해서는 어떻게 해야 하는지 출력하는 프로그램을 작성하시오.

보유 중인 금품의 양이 음수가 될 수 있다. 최대한 유리한 경로 또는 최적의 경로는 민승이네 집에서 출발하여 코레스코 콘도에 도착하는 경로 중 금품의 양이 최대가 되는 경로이다.

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

제한 사항

풀이

문제를 요약하면 1에서 시작하여 N까지 이동할 때 가장 금품을 많이 가진채 도달하는 경로를 구하는 것이다.

이때 특정 간선은 음수 가중치를 포함하고 있다.

보통 최단 경로나 최적 경로를 구하기 위해서는 다익스트라를 이용하는 경우가 많다.

하지만 다익스트라는 음수 가중치를 가진 그래프를 처리하지 못한다.

따라서 해당 문제는 다른 벨만 포드 알고리즘을 통해 경로를 계산해야 한다.

벨만 포드 알고리즘은 또 다른 특징이 하나 있다.

바로 음수 사이클을 탐지할 수 있다는 것이다.

벨만 포드 알고리즘은 N-1번의 라운드를 통해 모든 간선을 순회하며 최단 경로를 계산한다.

여기에 추가로 한 번의 라운드를 더 진행하였을 때 값이 바뀐다면 음수 사이클이 존재한다는 뜻이 된다.

이를 정답을 구하는데 이용할 수 있다.

정답이 될 수 있는 경로는 금품을 최대한 많이 남기는 것이다.

즉, 가중치를 음수로 변경하여 최단 경로를 구하면 가장 금품을 많이 획득하는 경로를 구할 수 있다.

하지만 음수 사이클이 존재한다면 최적 경로를 구할 수 없게 된다.

단 주의할 점은 음수 사이클이 존재하더라도 다른 경로가 있다면 최적 경로를 구할 수 있기도 하다.

따라서 음수 사이클이 존재하면서 N까지 도달 가능한 노드가 있는지 파악해야 한다.

그리고 1에서 N까지 가는 경로가 없을 때도 최적 경로가 존재하지 않는다.

이러한 조건들을 확인하면서 경로를 구하면 된다.

우선 시작 노드에서 도달 여부와 음수 사이클에서의 도달 여부를 모두 처리하기 위해 N에서 부터 시작하여 경로를 역으로 추적하는 방법을 사용할 수 있다.

for (int i = 0; i < M; i++)
{
    int a, b, c;
    cin >> a >> b >> c;

    revAdj[b].push_back(a);
    edges.push_back({ a,b,-c });
}

void CheckReach()
{
    queue<int> q;
    q.push(N);
    
    while (!q.empty())
    {
        auto current = q.front();
        q.pop();
      
        if (visited[current]) continue;
        visited[current] = true;
      
        for (auto& next : revAdj[current])
        {
            if (visited[next]) continue;
            q.push(next);
        }
    }
}

이후 벨만 포드 알고리즘을 통해 최단 경로를 계산한다.

dist[1] = 0;
for (int i = 0; i < N - 1; i++)
{
    for (auto& [a, b, c] : edges)
    {
        if (dist[b] > dist[a] + c)
        {
            dist[b] = dist[a] + c;
            pre[b] = a;
        }
    }
}

추가로 한 번의 라운드를 더 진행하여 음수 사이클을 확인하고 만약 해당 노드에서 N까지 도달할 수 있다면 최적 경로가 존재하지 않는다고 할 수 있다.

for (auto& [a, b, c] : edges)
{
    if (dist[b] > dist[a] + c)
    {
        // 음수 사이클
        if (visited[a])
        {
            cout << -1 << '\n';
            return 0;
        }
    }
}

그렇지 않으면 이전에 기록해 놓은 경로를 출력하면 된다.

void Print(int n) 
{
    if (n == 0) return;
    
    Print(pre[n]);
    cout << n << ' ';
}

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int N, M;
vector<tuple<int, int, int>> edges;
vector<vector<int>> revAdj;
vector<bool> visited;
vector<int> dist;
vector<int> pre;


void CheckReach()
{
	queue<int> q;
	q.push(N);

	while (!q.empty())
	{
		auto current = q.front();
		q.pop();

		if (visited[current]) continue;
		visited[current] = true;

		for (auto& next : revAdj[current])
		{
			if (visited[next]) continue;
			q.push(next);
		}
	}
}

void Print(int n) 
{
	if (n == 0) return;

	Print(pre[n]);
	cout << n << ' ';
}

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> N >> M;
	
	revAdj.resize(N + 1, vector<int>());
	visited.resize(N + 1, false);
	dist.resize(N + 1, MAX);
	pre.resize(N + 1);

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		revAdj[b].push_back(a);
		edges.push_back({ a,b,-c });
	}

	CheckReach();

	if (!visited[1]) 
	{
		cout << -1 << '\n';
		return 0;
	}

	dist[1] = 0;
	for (int i = 0; i < N - 1; i++)
	{
		for (auto& [a, b, c] : edges)
		{
			if (dist[b] > dist[a] + c)
			{
				dist[b] = dist[a] + c;
				pre[b] = a;
			}
		}
	}

	// check
	for (auto& [a, b, c] : edges)
	{
		if (dist[b] > dist[a] + c)
		{
			// 음수 사이클
			if (visited[a])
			{
				cout << -1 << '\n';
				return 0;
			}
		}
	}

	Print(N);

	return 0;
}