[백준 31230] 모비스터디 - JAVA

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

 

다익스트라로 최단 경로를 구하고, 최단 경로에서 거쳐간 노드 번호를 출력하는 문제다.

 

 

접근 방법의 실패

dist(A-> i, B -> i)는 dist(i -> A, i -> B)와 동치다. 

그래서 모든 정점 Vi에 대해 dist(Vi -> A, Vi -> B)를 구하려 했다. 이는 불필요하다.

정점 A, B의 탐색 2번 만으로 구할 수 있다.

 

이후 해당 글을 참고했다.

https://cjh970422.tistory.com/entry/BOJ%EB%B0%B1%EC%A4%80-31230-%EB%AA%A8%EB%B9%84%EC%8A%A4%ED%84%B0%EB%94%94

 

배운 것

 

1. 거쳐간 노드를 찾기 위해 탐색에 경로를 같이 저장할 필요가 없다. (불가능할 정도로 복잡도가 커짐)

2. 어떤 경로가 최단(min(dist))인지 판단할 때 min(A -> B)를 기준으로 삼는다. (dist 배열에서 O(n)으로 찾을 필요가 없다.)

dist[A][B]  == dist[A][i] + dist[B][i] 를 만족하는 i를 찾으면 된다.

3. static 선언 시 입출력 관련 객체와 로직 관련 값을 분리해 놓는다. (가독성 약간 증가)

4. List<> = new ArrayList<>(); 꼴의 다형성 선언도 반드시 할 필요는 없다.

 

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

class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static StringTokenizer st;
  static StringBuilder sb = new StringBuilder();

  static class Node implements Comparable<Node> {

    int num;
    long weight;

    Node(int num, long weight) {
      this.num = num;
      this.weight = weight;
    }

    @Override
    public int compareTo(Node n) {

      return Long.compare(this.weight, n.weight);
    }
  }

  static void solve(int P, int num) {

    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(num, 0));

    while (!pq.isEmpty()) {

      Node cur = pq.poll();

      if (dist[P][cur.num] < cur.weight) {
        continue; // 가지치기 - 안하면 시간 초과
      }

      for (Node next : edge[cur.num]) {

        long compWeight = dist[P][cur.num] + next.weight;

        if (compWeight < dist[P][next.num]) {
          dist[P][next.num] = compWeight;
          pq.offer(new Node(next.num, compWeight));
        }
      }
    }
  }

  static int N, M, A, B;
  static long[][] dist;
  static ArrayList<Node>[] edge;

  public static void main(String[] args) throws IOException {

    st = new StringTokenizer(br.readLine());

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

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

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

      edge[from].add(new Node(to, weight));
      edge[to].add(new Node(from, weight));
    }

    // 0 -> A, 1 -> B
    dist = new long[2][N + 1];
    long MAX = Long.MAX_VALUE / 2;
    Arrays.fill(dist[0], MAX);
    Arrays.fill(dist[1], MAX);
    dist[0][A] = 0;
    dist[1][B] = 0;

    // 구현
    solve(0, A);
    solve(1, B);

    int cnt = 0;
    long minDis = dist[0][B]; // equals to dist[1][A];
    for (int i = 1; i <= N; i++) {

      if (dist[0][i] + dist[1][i] == minDis) {
        sb.append(i).append(" ");
        cnt++;
      }
    }

    System.out.println(cnt);
    System.out.println(sb);
  }
}