Dev 일기장

1. 문제

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

문제 설명

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

제한 사항

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

입출력 예

2. 어떻게 풀까?

• 처음 답
  • 주어진 입력으로 인접리스트를 만든다.
  • Dijkstra 알고리즘을 이용하여 각 지점에서 X지점까지의 최단거리를 구한다.
  • Dijkstra 알고리즘을 이용하여 X지점에서 각 지점까지의 최단거리를 구한다.
  • 가장 값이 큰 값을 출력한다.

• 다른 답 참고
  • 인접리스트를 만들 때, from -> to의 정보를 to -> from 역방향 인접리스트를 하나 더 만든다.
  • 각 지점에서 X지점까지 최단거리는 역방향 인접리스트에서 보면 X지점에서 각 지점까지의 최단거리와 같다.
  • 그러므로
    • 각 지점에서 X지점까지 최단거리는 역방향 인접리스트를 이용하고
    • X지점에서 각 지점까지는 인접리스트를 이용한다.
  • 그 이후는 같다.

3. 코드

처음 답안 코드

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

 class Main {

  private static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));
  private static final BufferedWriter WRITER = new BufferedWriter(new OutputStreamWriter(System.out));
  private static StringTokenizer tokenizer;
  private static int vertexCount;

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

    List<Edge>[] adjList = new List[vertexCount + 1];
    for (int i = 1; i <= vertexCount; i++) {
      adjList[i] = new ArrayList<>();
    }
    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());

      adjList[from].add(new Edge(to, weight));
    }

    int max = Integer.MIN_VALUE;
    for (int i = 1; i <= vertexCount; i++) {
      int distance = dijkstra(adjList, i, destination) + dijkstra(adjList, destination, i);
      max = Math.max(max, distance);
    }

    WRITER.write(max + "");
    WRITER.flush();
    WRITER.close();
    READER.close();

  }

  private static int dijkstra(List<Edge>[] adjList, int source, int destination) {
    PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
    int[] distance = new int[vertexCount + 1];
    Arrays.fill(distance, Integer.MAX_VALUE);
    boolean[] visit = new boolean[vertexCount + 1];
    queue.add(new Edge(source, 0));
    distance[source] = 0;

    while (!queue.isEmpty()) {
      Edge currentEdge = queue.poll();

      for (Edge adjEdge : adjList[currentEdge.to]) {
        if (distance[adjEdge.to] > distance[currentEdge.to] + adjEdge.weight) {
          distance[adjEdge.to] = distance[currentEdge.to] + adjEdge.weight;
          queue.add(new Edge(adjEdge.to, distance[adjEdge.to]));
        }
      }
    }

    return distance[destination];
  }
}

class Edge {

  int to;
  int weight;

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

다른 답 참고한 코드

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

 class Main {

  private static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));
  private static final BufferedWriter WRITER = new BufferedWriter(new OutputStreamWriter(System.out));
  private static StringTokenizer tokenizer;
  private static int vertexCount;
  private static int edgeCount;

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

    List<Edge>[] adjList = new List[vertexCount + 1];
    List<Edge>[] reverseAdjList = new List[vertexCount + 1];

    buildAdjList(adjList, reverseAdjList);

    int max = Integer.MIN_VALUE;
    int[] go_distance = dijkstra(reverseAdjList, destination);
    int[] back_distance = dijkstra(adjList, destination);

    for (int i = 1; i <= vertexCount; i++) {
      max = Math.max(max, go_distance[i] + back_distance[i]);
    }

    WRITER.write(max + "");
    WRITER.flush();
    WRITER.close();
    READER.close();

  }

  private static void buildAdjList(List<Edge>[] adjList, List<Edge>[] reverseAdjList)
      throws IOException {
    for (int i = 1; i <= vertexCount; i++) {
      adjList[i] = new ArrayList<>();
      reverseAdjList[i] = new ArrayList<>();
    }
    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());

      adjList[from].add(new Edge(to, weight));
      reverseAdjList[to].add(new Edge(from, weight));
    }
  }

  private static int[] dijkstra(List<Edge>[] adjList, int source) {
    PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
    int[] distance = new int[vertexCount + 1];
    Arrays.fill(distance, Integer.MAX_VALUE);
    queue.add(new Edge(source, 0));
    distance[source] = 0;

    while (!queue.isEmpty()) {
      Edge currentEdge = queue.poll();

      for (Edge adjEdge : adjList[currentEdge.to]) {
        if (distance[adjEdge.to] > distance[currentEdge.to] + adjEdge.weight) {
          distance[adjEdge.to] = distance[currentEdge.to] + adjEdge.weight;
          queue.add(new Edge(adjEdge.to, distance[adjEdge.to]));
        }
      }
    }

    return distance;
  }
}

class Edge {

  int to;
  int weight;

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

4. 느낀 점

• 처음엔 Dijkstra 알고리즘만 알면 쉽게 풀 수 있는 문제라고 생각했는데 역방향 리스트를 만들어서 더 효율적으로 해결한 답을 보고 이런 방법도 있다는 것을 알 수 있었다. 알아 둬야겠다.
• BellmanFord나 Floyd 알고리즘으로도 해결 할 수 있을듯