[백준] 1738번 골목길

문제: 1738번: 골목길

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m; // n: 교차 지점 수(정점), m: 골목길의 개수(간선)
	cin >> n >> m;
	vector<pair<pair<int, int>, int>> edges; // 간선들 저장해놓기
	vector<vector<int>> reverseEdges(n + 1); // 역방향 간선들 저장해놓기(정점 n 에 도달할 수 있는 노드들을 찾기 위함.
	vector<int> prev(n + 1); // 이전 정점 저장해놓기

	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w; // u 번 교차점에서 v 번 교차점으로 이동할 수 있는 골목길, w 는 금품의 양
		
		// 답으로 코레스크 콘도에 도착하는 경로 중 금품의 양이 최대가 되는 경로를 원하므로 입력받은 가중치를 -1 랑 곱해줌
		// 이제 기존의 최단 거리 벨만포드 풀이를 이용하면 됨
		w = w * -1; 
		
		edges.push_back(make_pair(make_pair(u, v), w)); // 간선 저장

		reverseEdges[v].push_back(u); // 역방향 간선 저장(가중치는 필요 없음)
	}

	// 정점 n 과 연결되는 정점들 다 표시해놓기(음의 사이클이 이루어지는 곳의 정점이 정점 n 이랑 연결되면 -1 출력해야 하므로..)
	vector<int> conectedN(n + 1); // 정점 N 과 연결된 노드들 체크(0: 연결 안 됨, 1: 연결 됨)
	queue<int> q;
	q.push(n);
	conectedN[n] = 1; // 자기자신으로는 당연히 연결되어 있음..
	// 비어 있지 않을 때까지..
	while (!q.empty()) {
		int nodeNum = q.front();
		q.pop();

		for (int i = 0; i < reverseEdges[nodeNum].size(); i++) {
			int linkNode = reverseEdges[nodeNum][i]; // 지금 노드와 연결된 노드 번호 가져옴.
			if (conectedN[linkNode] == 0) {
				q.push(linkNode);
				conectedN[linkNode] = 1; // 연결 체크
			}
		}
	}

	// 민승이네 집은 1번 교차점, 코레스코 콘도는 n 번 교차점에 있음
	// 민승이네 집부터 코레스코 콘도까지 가는 동안 거치게 되는 교차점들의 번호를 차례로 출력
	vector<int> distance((n + 1), INT_MAX); // 0번 인덱스는 안 씀
	distance[1] = 0; // 민승이 집에서 민승이 집은 0..


	// 반복문을 n-1 번 돌아야함.
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m; j++) {
			// 모든 간선을 다 돌면서 거리값 업데이트 해야함
			pair<pair<int, int>, int> edge = edges[j];
			int u = edge.first.first; // 시작
			int v = edge.first.second; // 끝
			int w_uv = edge.second; // 가중치

			if ((distance[u] != INT_MAX) && ((distance[u] + w_uv) < distance[v])) {
				distance[v] = distance[u] + w_uv;
				prev[v] = u; // 이전 정점 저장
			}
		}
	}

	bool minusCycle = false;
	int cycleNum = -1;
	for (int i = 0; i < m; i++) {
		// 모든 간선을 다 돌면서 거리값 업데이트 해야함
		pair<pair<int, int>, int> edge = edges[i];
		int u = edge.first.first; // 시작
		int v = edge.first.second; // 끝
		int w_uv = edge.second; // 가중치

		// 음의 사이클!
		// 이게 정점 n 이랑 연결되는지 확인!
		if ((distance[u] != INT_MAX) && ((distance[u] + w_uv) < distance[v])) {
			if (connected[u] == 1 || conectedN[v] == 1) {
				minusCycle = true;
				cycleNum = v;
			}
		}
	}


	stack<int> output;
	output.push(n); // 처음으로 n 값 넣기
	if (minusCycle) {
		if (conectedN[cycleNum])
			cout << -1 << "\n";
	}
	else {
		int start = n;
		while (prev[start] != 1) {
			output.push(prev[start]);
			start = prev[start];
		}
		output.push(1); // 마지막으로 1 넣기

		while (!output.empty()) {
			int num = output.top();
			output.pop();
			cout << num << " ";
		}
	}


	return 0;
}

 

어제 풀었던 벨만 포드 기본 문제랑은 또 다르게 응용하는 문제였다.

 

문제에서 민승이네 집에서 출발하여 코레스코 콘도에 도착하는경로 중 금품의 양이 최대가 되는 경로를 찾으라고 하였는데 지금 최대가 되는 경로를 찾는 거니까 입력으로 받는 가중치의 값에 -1 을 곱해주면 다시 최소가 되는 경로를 찾는 문제로 바뀐다. 즉 입력값의 가중치에 -1 을 곱해서 받는 방법으로 이제 다시 벨만 포드 알고리즘을 이용할 수 있다.

 

 

근데 이 문제는 어제 풀었던 문제와는 다른게 음의 사이클이 존재한다고 해서 -1 을 출력하는 것이 아니다.

출력
최적의 경로를 구할 수 있다면 민승이네 집부터 코레스코 콘도까지 가는 동안 거치게 되는 교차점들의 번호를 공백 하나를 사이에 두고 차례로 출력하면 된다. 그런데, 경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생한다. 어떠한 경우에 그런 상황이 발생하는지 생각해 보자. 그러한 경우에는 -1을 출력하도록 한다.최적의 경로가 여러 개 존재할 때는 아무거나 출력해도 된다.

 

즉, 출력 조건을 보면 음의 사이클이 존재한다고 해서 바로 -1을 출력하는 것이 아니라, 정점 n 과 음의 사이클이 연결될 때 비로소 -1 을 출력하는 것이다. 즉, 다시 말하면 음의 사이클이 존재하더라도 정점 n 과 연결되어 있지 않으면 -1 을 출력하지 않고 민승이네 집에서 코레스코 콘도로가는 경로를 출력하는 것이다.

 

 

그러면 음의 사이클이랑 해당 정점이 연결되어 있는지의 여부를 어떻게 알 수 있는가? 바로 간선을 입력 받을 때 reverse 간선도 하나 만들어서 따로 저장해놓는다. 그리고 이 배열을 이용해서 정점 n 이랑 연결되어 있는 정점들을 conected 배열에 체크해놓는다. 그래서 나중에 음의 사이클이랑 정점 n 이랑 연결되어 있는지를 판단한다.   

 

 

마지막으로는 이제 해당 정점으로 가는 경로를 출력해야 하는 것이므로 prev 배열을 이용하여 해당 정점부터 역추적하여 스택에 차곡차곡 넣고, 마지막으로 다시 스택 요소를 하나씩 빼서 출력하면 된다. 경로를 출력하는 문제는 이번이 처음이었어서 새로운 걸 알게 된 것 같아 좋았다. 조금 어렵지만 복습할 때 스스로 다시 풀어봐야겠다.

 

 

 

참고자료: 

[백준/C++] 1738번: 골목길(G2)

[백준/C++] 1738번: 골목길(G2)