백준 1238 파티 Java

알고리즘 분류 : 최단 거리, 다익스트라

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

요약

두 노드 사이에 가중치(시간)가 있는 그래프이므로 BFS를 이용한 최단 거리 탐색은 사용할 수 없다. 하지만 음의 간선은 존재하지 않으므로 이 경우 대표적인 다익스트라 알고리즘을 이용하여 풀 수 있다. 다익스트라는 한 노드에서 다른 모든 노드 사이의 최단 거리를 구할 수 있다는 점을 기억하면 불필요한 연산을 줄일 수 있다.

풀이

다익스트라는 한 노드에서 다른 모든 노드 사이의 최단 거리를 O(ElogV)로 구할 수 있다.

여기서 구해야 하는 최단 거리는 두 가지이다.

1. 파티를 개최한 마을에서 다른 모든 마을로 이동하는 최단 거리
2. 다른 모든 마을에서 파티를 개최한 마을로 이동하는 최단 거리

방향이 존재하는 단방향 그래프이므로 파티를 갈 때와 집에 다시 돌아올 때 경로가 달라질 수도 있다는 점을 주의하자.

파티를 개최한 마을에서 다른 모든 마을로 이동하는 최단 거리는 파티를 개최한 마을에서 시작하는 다익스트라 알고리즘 한 번 만으로도 모두 계산할 수 있다. 그럼 다른 모든 마을에서 파티를 개최한 마을로 이동하는 최단 거리는 모든 마을에서 모두 다익스트라 알고리즘을 돌려봐야 할까?

다른 모든 마을에서 파티를 개최한 마을로 이동하는 최단 거리를 구할 때도 다익스트라 1번으로 구할 수 있다. 입력받은 모든 도로의 방향을 반대로 바꾼 후 파티를 개최한 마을에서 다른 모든 마을까지의 최단 거리를 구하면 된다.

따라서 다익스트라 알고리즘 한 번으로 한 노드에서 다른 모든 노드 사이의 최단 거리를 구할 수 있다는 점만 기억하면 불필요한 연산을 줄일 수 있다.

코드

public class Main {
  static int N; //마을 수
  static int M; //도로 수
  static int X; //파티 장소

  static List<List<Node>> roadInfo = new ArrayList<>();
  public static void main(String[] args) throws Exception {
    getInput();
    
    int[] goToHome = dijkstra(X);

    flipRoad();

    int[] goToParty = dijkstra(X);

    int maxTime = 0;
    for (int i = 0; i < N; i++) {
      maxTime = Math.max(maxTime, goToParty[i] + goToHome[i]);
    }

    System.out.println(maxTime);
  }

  static void flipRoad() throws Exception {
    List<List<Node>> flipRoadInfo = new ArrayList<>();

    for (int i = 0; i < N; i++) {
      flipRoadInfo.add(new ArrayList<>());
    }

    for (int i = 0; i < roadInfo.size(); i++) {
      List<Node> currentRoadInfo = roadInfo.get(i);

      for (int j = 0; j < currentRoadInfo.size(); j++) {
        flipRoadInfo.get(currentRoadInfo.get(j).position).add(new Node(i, currentRoadInfo.get(j).time));
      }
    }

    roadInfo = flipRoadInfo;
  }

  static void getInput() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    N = line[0];
    M = line[1];
    X = line[2] - 1;

    for (int i = 0; i < N; i++) {
      roadInfo.add(new ArrayList<>());
    }

    for (int i = 0; i < M; i++) {
      line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
      int start = line[0] - 1; //인덱스는 1 빼기
      int end = line[1] - 1;
      int time = line[2];
      roadInfo.get(start).add(new Node(end, time));
    }
  }

  static int[] dijkstra(int start) {
    PriorityQueue<Node> pq = new PriorityQueue<>();

    int[] minTable = new int[N];
    for (int i = 0; i < N; i++) {
      minTable[i] = Integer.MAX_VALUE;
    }

    minTable[start] = 0;
    pq.add(new Node(start, 0));

    while (!pq.isEmpty()) {
      Node current = pq.poll();

      if (minTable[current.position] < current.time) {
        continue;
      }

      List<Node> currentRoadInfo = roadInfo.get(current.position);
      for (Node n : currentRoadInfo) {
        int nearNodePosition = n.position;
        int roadTime = n.time;

        if (minTable[nearNodePosition] > current.time + roadTime) {
          minTable[nearNodePosition] = current.time + roadTime;
          pq.add(new Node(nearNodePosition, minTable[nearNodePosition]));
        }
      }
    }

    return minTable;
  }

  static class Node implements Comparable<Node> {
    int position;
    int time;

    public Node(int position, int time) {
      this.position = position;
      this.time = time;
    }


    @Override
    public int compareTo(Node n) {
      return n.time - this.time;
    }
  }
}

도로를 뒤집지 않고 다익스트라를 하면 각자 마을로 돌아갈 수 있는 최단거리이다. 도로의 방향을 뒤집은 후 다익스트라를 하면 각자 마을에서 파티 장소로 갈 수 있는 최단 거리이다. 다익스트라 알고리즘은 우선순위 큐 방식을 이용한 알고리즘으로 구현하였다.

시행착오

처음에 다익스트라가 모든 노드의 최단 거리를 구할 수 있다는 점을 간과하여 다음과 같이 각 마을에서 파티 장소까지 다익스트라 N번, 파티 장소에서 마을까지 다익스트라 N번을 해버리는 엄청난 실수를 하고 말았다..

        for (int i = 0; i < N; i++) {
            maxTime = Math.max(maxTime, dijkstra(i, X) + dijkstra(X, i));
        }

이렇게 하니 당연히 메모리 초과로 채점조차 되지 않았다. 다익스트라 알고리즘에 대한 이해가 부족했던 것 같다.

Reference

https://minhamina.tistory.com/198