[백준/골드2]1738.골목길

문제

---

문제

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

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

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

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

입력

첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어진다. 이는 u번 교차점에서 v번 교차점으로 이동할 수 있는 골목길이 나있다는 의미이다. 즉, 주어지는 골목길들은 기본적으로 모두 일방통행로이다. w (0 ≤ |w| ≤ 1,000)는 이 길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이다. 음수는 갈취, 양수는 획득을 뜻한다.

골목길의 교차점 번호는 1이상 n이하의 정수이다. 민승이네 집은 1번 교차점에 있고, 이곳 코레스코 콘도는 n번 교차점에 있다.

출력

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

최적의 경로가 여러 개 존재할 때는 아무거나 출력해도 된다.

풀이

---

접근 방법

• 전형적인 벨만-포드 문제라고 생각함 ⇒ 경로가 음수, 양수 둘 다 존재함 ⇒ 최단거리가 아니라 최적 경로를 찾는 거라 가장 돈을 많이 버는 경로를 찾음. 양의 사이클이 존재함
• 콘도까지 가는 길은 항상 존재한다고 가정하고 문제를 풀었다.
• 그런데, 경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생한다. 어떠한 경우에 그런 상황이 발생하는지 생각해 보자.  ⇒ 예제 2번을 보고 그려봤다.
  • 양의 사이클이 존재하는 경우 ⇒ -1 출력
  • 양의 사이클이 존재한다는 것은 N번째 라운드에서 업데이트가 일어난다는 것

• 하지만 아래와 같은 경우에는 양의 사이클이 존재하지만 3을 출력해야 한다.
  • 양의 사이클이 정점 N과 연결되어 있으면 -1 출력 ⇒ DFS로 연결되어 있는지 확인
  • 그렇지 않으면 경로를 출력
  •  
• 경로를 어떻게 출력할 것인가? 이 부분이 나는 까다로웠다.
  • 내가 가는 경로가 다음 노드로 가는 최적의 경로일 때만 간다(DFS로)
  • 시작점부터 원하는 점에 도착할 때까지 반복. 도착한다면 지금까지 온 경로(Trace)를 출력

• 시간초과가 나길래 인접리스트로 간선들을 저장하고 사용했다.

코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

// [1738] 골목길
// 벨만 포드 
// 음의 사이클 -> 양의 사이클
// 양의 사이클이 생기면 -1 출력
// 양의 사이클이 안생기면 -> 첫점에서 끝점까지 DFS하면서 끝점 도착했을 때 거리 합이랑 Dist[end] 랑 같으면 그 경로를 출력

public class baekjoon_1738 {
	static long[] Dist;
	static int N, M;
	static final int NINF = Integer.MIN_VALUE;
	static ArrayList<Data>[] adjList;
	static boolean[] visited;
	static int[] trace;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		adjList = new ArrayList[N + 1];

		for (int i = 1; i <= N; i++) {
			adjList[i] = new ArrayList<Data>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			adjList[from].add(new Data(to, weight));
		}

		boolean positiveCycle = bellmanford();

		if (positiveCycle) {
			System.out.println(-1);
		} else {
			visited = new boolean[N + 1];
			visited[1] = true;
			trace = new int[N + 1];
			trace[0] = 1;
			findTrace(1, 0, 1);
		}

	}

	// dfs로 찾아본다
	// 지금 가는 길이 최적 경로일 때만 재귀 돌림
	private static void findTrace(int from, long dist, int order) {
		if (from == N) {
			for(int i = 0; i<order; i++) {
				System.out.print(trace[i] + " ");
			}
			System.exit(0);
		}

		for (Data edge : adjList[from]) {
			if (!visited[edge.to] && Dist[edge.to] == (Dist[from] + edge.weight)) {
				visited[edge.to] = true;
				trace[order] = edge.to;
				findTrace(edge.to, Dist[from] + edge.weight, order + 1);
			}
		}
	}

	private static boolean bellmanford() {
		Dist = new long[N + 1];

		// Dist[1] = 0; // 시작점
		for (int i = 2; i <= N; i++) {
			Dist[i] = NINF;
		}

		// 정점 개수만큼 round
		for (int round = 0; round < N; round++) {
			// 모든 간선을 다 돌면서 확인해 본다.
			for (int i = 1; i <= N; i++) {
				for (Data edge : adjList[i]) {
					if (Dist[edge.to] < Dist[i] + edge.weight) {
						Dist[edge.to] = Dist[i] + edge.weight;

						if (round == N - 1) {
							visited = new boolean[N + 1];
							visited[i] = true;
							if (cycleConnected(i)) { // 양의 서클이 존재하는데 그게 도착 노드와 연결되어있으면 안됨!
								return true;
							}
						}
					}
				}
			}
		}
		return false;
	}

	private static boolean cycleConnected(int from) {
		// 도착노드와 연결되어 있으면
		if (from == N) {
			return true;
		}
		boolean flag = false;

		for (Data edge : adjList[from]) {
			if (!visited[edge.to]) {
				visited[edge.to] = true;
				flag |= cycleConnected(edge.to);
			}
		}
		return flag;
	}

	private static class Data {
		int to;
		int weight;

		public Data(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}
	}
}