취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1738번 문제인 골목길이다.
문제는 아래 링크를 확인하자.

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

주어진 그래프에서 도착점으로 도착할 수 없거나 "무한히 돌면서 돈을 벌 수 있는, 출발점에서 들어올 수 있고 도착점으로 빠져나갈 수 있는 사이클"이 존재한다면 -1을, 그렇지 않다면 출발점에서 도착점까지 가는 최단경로를 출력하는 문제이다.

이를 판단하기 위해 Bellman-Ford 알고리즘을 이용하자.

사이클에서 도착점으로 이동할 수 있는가를 판단할 때, Bellman-Ford의 relaxation을 이용하여 구현하면 다음과 같은 노드 100개짜리 데이터를 뚫기 어렵게 된다. 주어진 사이클을 몇 바퀴 돌아야하는지를 생각해보자.

• 1->2, 2->3, ..., 49->50의 -1000의 가중치를 가진 에지들
• 50~99번 노드로 구성된 가중치가 1인 양의 사이클
• 50->100의 -1000의 가중치를 가진 에지
• 1->100의 1000의 가중치를 가진 에지

따라서, 사이클을 이루는 노드에서 DFS나 BFS 등의 그래프탐색을 통해 도착점으로 갈 수 있는지를 판단하는 것이 좋다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

struct edge {
	int x, y;
	ll d;
	edge(int x, int y, ll d) {
		this->x = x, this->y = y, this->d = d;
	}
};

vector<int> G[101];
bool iscycle[101];
bool visited[101];
int parent[101];
ll dist[101];
vector<edge> edges;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	while (M--) {
		int x, y, w; cin >> x >> y >> w;
		edges.emplace_back(edge(x, y, -w));
		G[x].emplace_back(y);
	}

	visited[1] = 1;
	for (int i = 1; i < N; i++) {
		for (auto& e : edges) {
			if (visited[e.x]) {
				if (visited[e.y]) {
					if (dist[e.y] > dist[e.x] + e.d) {
						dist[e.y] = dist[e.x] + e.d;
						parent[e.y] = e.x;
					}
				}
				else {
					visited[e.y] = 1;
					dist[e.y] = dist[e.x] + e.d;
					parent[e.y] = e.x;
				}
			}
		}
	}

	for (auto& e : edges) {
		if (visited[e.x]) {
			if (visited[e.y]) {
				if (dist[e.y] > dist[e.x] + e.d) iscycle[e.x] = 1;
			}
		}
	}

	queue<int> que;
	for (int i = 1; i <= N; i++) if (iscycle[i]) que.push(i);
	while (!que.empty()) {
		int current = que.front(); que.pop();
		for (auto node : G[current]) {
			if (iscycle[node]) continue;
			iscycle[node] = 1;
			que.push(node);
		}
	}

	if (iscycle[N] || !visited[N]) cout << -1;
	else {
		vector<int> stk;
		while (N > 1) {
			stk.emplace_back(N);
			N = parent[N];
		}
		cout << 1;
		while (!stk.empty()) {
			cout << ' ' << stk.back();
			stk.pop_back();
		}
	}
}