백준 1738

●문제 출처

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

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

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

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

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

●코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;

    static class Edge {
        int start;
        int end;
        int cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }

    static long[] distance;
    static int[] parent;
    static List<Edge> edges;

    static List<Integer>[] graph;
    static List<Integer>[] reverseGraph;
    static boolean[] fromStart;
    static boolean[] toEnd;

    static void bfs(int start, List<Integer>[] g, boolean[] visited) {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int now = q.poll();

            for (int next : g[now]) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.offer(next);
                }
            }
        }
    }

    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());

        edges = new ArrayList<>();
        distance = new long[n + 1];
        parent = new int[n + 1];
        graph = new ArrayList[n + 1];
        reverseGraph = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }

        Arrays.fill(distance, Long.MIN_VALUE);

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edges.add(new Edge(u, v, w));
            graph[u].add(v);
            reverseGraph[v].add(u);
        }

        fromStart = new boolean[n + 1];
        toEnd = new boolean[n + 1];

        bfs(1, graph, fromStart);
        bfs(n, reverseGraph, toEnd);

        distance[1] = 0;

        boolean infinite = false;

        for (int i = 1; i <= n; i++) {
            for (Edge now : edges) {
                if (distance[now.start] == Long.MIN_VALUE) continue;

                if (distance[now.end] < distance[now.start] + now.cost) {
                    distance[now.end] = distance[now.start] + now.cost;
                    parent[now.end] = now.start;

                    if (i == n && fromStart[now.end] && toEnd[now.end]) {
                        infinite = true;
                    }
                }
            }
        }

        if (distance[n] == Long.MIN_VALUE || infinite) {
            System.out.println(-1);
            return;
        }

        List<Integer> path = new ArrayList<>();
        int cur = n;

        while (cur != 0) {
            path.add(cur);
            if (cur == 1) break;
            cur = parent[cur];
        }

        Collections.reverse(path);

        StringBuilder sb = new StringBuilder();
        for (int x : path) {
            sb.append(x).append(' ');
        }
        System.out.println(sb);
    }
}

●느낀 점

• 처음 풀이 방식

  벨만-포드 알고리즘을 활용하여
  distance[now.end]<distance[now.start]+now.cost
  조건에 맞는 값을 없데이트 시켜주고
  마지막 정점을 시작으로 끝 정점을 가르키는 시작 정점 중 distance 값이 큰 값을 저장하여 출력하도록하였다.
  하지만, 크다고 저장하면 안되었다....

• 두번째 풀이 방식

  (distance[prev] + now.cost == distance[now])
  조건에 맞는 식으로 하였지만,
  여기서 distance[prev] + cost == distance[cur] 를 만족하는 정점이 여러 개일 수 있어서,
  잘못 고르면 1로 안 가고 사이클처럼 빙빙 돌 수 있습니다.

• 마지막 풀이 방식

  parent[now.end] = now.start으로 기록하여
  푸는 방식!!

음 생각을 좀 잘하면 쉬운데 너무 돌아간 거 같다 ㅎㅎ...