[C++] 백준 1738 : 골목길

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

1738번: 골목길

백준 1738번 골목길 문제를 풀었다.

 

특정 노드에서 특정 노드로 감 && 간선에 음의 가중치가 있음 -> 벨만 포드로 풀어야 겠다고 생각했다.

문제의 입력에서 cost에 -를 붙여서 음의 사이클 문제로 바꿨다.

 

문제를 풀기 위해 어떤 경우에 -1을 출력하고 어떤 경우에 경로를 출력하는지 생각해봤다.

 

1. 출발지점(1)에서 도착지점(n)까지 도달하는 경로가 없을 때 -> -1 출력

2. 출발지점(1)에서 도착지점(n)까지 도달하는 경로가 있을 때

2-1. 음의 사이클이 존재하고 음의 사이클에서 도착 지점까지 가는 경로가 있을 때 -> -1 출력

2-2. 음의 사이클이 존재하지만 음의 사이클에서 도착 지점까지 가는 경로가 없을 때 -> 경로 출력

 

위와 같이 경우의 수를 나누고 문제를 풀었다.

	int flag = 0;
	for (int i = 0; i < edges.size(); i++) {
		Edge temp = edges[i];
		int start = temp.start;
		int end = temp.end;
		int cost = temp.cost;
		long long next_cost = cost + dist[start];
		if (dist[start] == INF)
			continue;
		if (dist[end] > next_cost) {
			if (Dijkstra(n, start, n)) {
				flag = 1;
				break;
			}
		}
	}

위의 코드는 n번째 라운드 때 음의 사이클이 발생하는지 확인하는 코드다.

음의 사이클이 존재했을 때 다익스트라 알고리즘을 사용해서 음의 사이클 시작 부분을 start로, 도착 지점(n)을 end로 넘겨줘서 경로를 탐색했다.

 

bool Dijkstra(int n, int start, int end) {
	priority_queue<Node, vector<Node>, compare> pq;
	vector<long long> d;
	d.assign(n + 1, INF);
	d[start] = 0;
	pq.push(Node(start, d[start]));

	while (!pq.empty()) {
		Node temp = pq.top();
		int cur = temp.end;
		int cost = temp.cost;
		pq.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			temp = v[cur][i];
			int next = temp.end;
			long long next_cost = cost + temp.cost;
			if (d[next] > next_cost) {
				d[next] = next_cost;
				pq.push(Node(next, next_cost));
			}
		}
	}

	if (d[end] == INF)
		return 0;
	else
		return 1;
}

다익스트라 코드에서 인자로 받은 start에서 end로 가는 경로를 찾는다.

만약 end로 가는 경로가 없다면 0을 반환한다. 이것은 음의 사이클이 존재하지만 도착 지점까지 가는 경로가 없다는 것이다. 다시 말해 출발 지점에서 도착 지점까지 도달하는 것과 음의 사이클이 존재하는 것이 아무 상관이 없다는 뜻이다.

end로 가는 경로가 있으면 1을 반환한다. 음의 사이클이 존재하고 도착 지점까지 가는 경로가 있다는 뜻이므로 -1을 출력해줘야 한다.

 

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;
#define INF 2000000000
struct Edge {
	int start;
	int end;
	int cost;
	Edge(){}
	Edge(int X, int Y, int Z) : start(X), end(Y), cost(Z) {}
};
struct Node {
	int end;
	int cost;
	Node() {}
	Node(int X, int Y) : end(X), cost(Y) {}
};
struct compare {
	bool operator()(Node a, Node b) {
		return a.cost > b.cost;
	}
};

int n, m;
vector<Edge> edges;
vector<long long> dist;
int prev_node[101];
vector<int> path;

vector<Node> v[101];

bool Dijkstra(int n, int start, int end) {
	priority_queue<Node, vector<Node>, compare> pq;
	vector<long long> d;
	d.assign(n + 1, INF);
	d[start] = 0;
	pq.push(Node(start, d[start]));

	while (!pq.empty()) {
		Node temp = pq.top();
		int cur = temp.end;
		int cost = temp.cost;
		pq.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			temp = v[cur][i];
			int next = temp.end;
			long long next_cost = cost + temp.cost;
			if (d[next] > next_cost) {
				d[next] = next_cost;
				pq.push(Node(next, next_cost));
			}
		}
	}

	if (d[end] == INF)
		return 0;
	else
		return 1;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		edges.push_back(Edge(start, end, -cost));
		v[start].push_back(Node(end, 1));
	}

	dist.assign(101, INF);
	dist[1] = 0;

	for (int i = 1; i <= n - 1; i++) {
		for (int j = 0; j < edges.size(); j++) {
			Edge temp = edges[j];
			int start = temp.start;
			int end = temp.end;
			int cost = temp.cost;
			long long next_cost = cost + dist[start];
			if (dist[start] == INF)
				continue;
			if (dist[end] > next_cost) {
				dist[end] = next_cost;
				prev_node[end] = start;
			}
		}
	}

	int flag = 0;
	for (int i = 0; i < edges.size(); i++) {
		Edge temp = edges[i];
		int start = temp.start;
		int end = temp.end;
		int cost = temp.cost;
		long long next_cost = cost + dist[start];
		if (dist[start] == INF)
			continue;
		if (dist[end] > next_cost) {
			if (Dijkstra(n, start, n)) {
				flag = 1;
				break;
			}
		}
	}

	
	if (dist[n] == INF) {
		cout << "-1";
	}
	else {
		if (flag == 1) {
			cout << "-1";
		}
		else {
			int temp = n;
			path.push_back(n);
			while (1) {
				temp = prev_node[temp];
				path.push_back(temp);
				if (temp == 1) {
					break;
				}
			}

			for (int i = path.size()-1; i >= 0; i--) {
				cout << path[i] << ' ';
			}
		}
	}



	return 0;

}