[백준] 1738. 골목길 (Java)

1. 문제

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

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. 어떻게 풀까

• 최단 경로 알고리즘을 이용해서 해결 할 수 있다.
• 이 문제의 경우 최솟값을 구하는게 아니라 최댓값을 구하는 것이므로 음수 사이클을 찾는 것이 아니라 양수 사이클을 찾아야 한다.
• 사이클이 형성되는지 확인 해야하므로 벨만 포드 알고리즘을 이용하여 해결했다.
  • 사이클이 존재하더라도 사이클이 목적지에 영향을 주지 않는다면 상관없다.
    • 이 점을 간과해서 틀렸다. ㅜ

 

3. 코드 (Java)

package baekjoon.shortest_path.골목길_20220318;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

  private static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));
  private static StringTokenizer tokenizer;

  private static int vertexCount;
  private static int edgeCount;
  private static int[][] edges;
  private static int[] distanceFromSource;
  private static int[] predecessor;

  public static void main(String[] args) throws IOException {
    tokenizer = new StringTokenizer(READER.readLine());
    vertexCount = Integer.parseInt(tokenizer.nextToken());
    edgeCount = Integer.parseInt(tokenizer.nextToken());

    init();
    bellmanFord();

    if (distanceFromSource[vertexCount] == Integer.MIN_VALUE) {
      System.out.println(-1);
      return;
    }

    for (int[] edge : edges) {
      int from = edge[0];
      int to = edge[1];
      int weight = edge[2];
      if (distanceFromSource[from] == Integer.MIN_VALUE) {
        continue;
      }

      if (isCycle(from, to, weight) && isCycleOnPath(to)) {
        System.out.println(-1);
        return;
      }
    }

    printShortestPath();
  }

  private static void init() throws IOException {
    edges = new int[edgeCount][];
    for (int i = 0; i < edgeCount; i++) {
      tokenizer = new StringTokenizer(READER.readLine());
      int from = Integer.parseInt(tokenizer.nextToken());
      int to = Integer.parseInt(tokenizer.nextToken());
      int weight = Integer.parseInt(tokenizer.nextToken());

      edges[i] = new int[]{from, to, weight};
    }

    distanceFromSource = new int[vertexCount + 1];
    predecessor = new int[vertexCount + 1];
    for (int i = 1; i <= vertexCount; i++) {
      distanceFromSource[i] = Integer.MIN_VALUE;
      predecessor[i] = -1;
    }
    distanceFromSource[1] = 0;
  }

  private static void bellmanFord() {
    for (int i = 0; i < vertexCount - 1; i++) {
      for (int[] edge : edges) {
        int from = edge[0];
        int to = edge[1];
        int weight = edge[2];
        if (distanceFromSource[from] == Integer.MIN_VALUE) {
          continue;
        }
        if (distanceFromSource[to] < distanceFromSource[from] + weight) {
          distanceFromSource[to] = distanceFromSource[from] + weight;
          predecessor[to] = from;
        }
      }
    }
  }

  private static boolean isCycle(int from, int to, int weight) {
    return distanceFromSource[to] < distanceFromSource[from] + weight;
  }

  private static boolean isCycleOnPath(int targetVertex) {
    boolean[] visit = new boolean[vertexCount + 1];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(targetVertex);

    while (!queue.isEmpty()) {
      int currentVertex = queue.poll();
      if (visit[currentVertex]) {
        continue;
      }
      visit[currentVertex] = true;

      for (int[] edge : edges) {
        int from = edge[0];
        int to = edge[1];

        if (from == currentVertex && !visit[to]) {
          queue.add(to);
        }
      }
    }

    return visit[vertexCount];
  }

  private static void printShortestPath() {
    StringBuilder sb = new StringBuilder();
    int index = vertexCount;
    sb.append(vertexCount);
    while (predecessor[index] != -1) {
      sb.insert(0, predecessor[index] + " ");
      index = predecessor[index];
    }
    System.out.print(sb.toString());
  }
}

• bellmanFord() 메소드를 통해 출발 노드부터 목적지 노드까지의 최단 경로를 구했다.
• 목적지 노드까지의 경로가 없거나, 경로상에 양수 사이클이 존재할 경우 -1를 출력하도록 했다.
• 경로 상에 양수 사이클이 존재하는지 검사했다.
  • 사이클이 존재하는 지 검증
    • 벨만 포드 알고리즘 이후에도 distanceFromSource가 갱신이 되는지 확인했다.
  • 사이클이 존재하고, 그 사이클이 경로상에 존재하는지 검증
    • 사이클이 존재하는 노드에서 목적지 노드까지의 경로가 있는지 BFS를 이용하여 확인했다.
    • 이 부분을 간과해서 틀렸다.
• predecessor과 backtracking을 이용해서 최단 경로를 출력했다.
  • 처음에는 StringBuilder에 append()로 하나씩 추가한 후 reverse()로 마무리를 했었는데 계속 실패가 나와서 insert()로 바꾸었다.

 

벨만 포드 알고리즘을 알고 있다면 쉽게 풀 수 있긴 한데, 음수(문제는 양수)사이클이 출발 노드에서 목적지 노드까지의 경로에 포함되는지 검사하는 로직이 반드시 필요하다는것을 간과했다.