[백준 1240] 노드사이의 거리 - JAVA

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

 

일반적인 그래프탐색 문제다.

 

플로이드-워셜도 시간복잡도 아슬하게 적용 가능하다.

(단, 트리이므로 경로가 유일해서 최단 경로 알고리즘은 비효율적이다.)

 

그래프 탐색간 틀린 이유

cost[][] 배열을 썼는데, 메모리 제한이 짠 문제여서 초과함 (경로가 유일하므로 min cost 배열 필요 없음)

 

풀이 1. BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

  static class Node {

    int a, v;

    Node(int a, int v) {
      this.a = a;
      this.v = v;
    }
  }

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

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

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

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

    for (int i = 0; i < N - 1; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());

      edge[a].add(new Node(b, v));
      edge[b].add(new Node(a, v));
    }

    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int from = Integer.parseInt(st.nextToken());
      int to = Integer.parseInt(st.nextToken());

      boolean[] vst = new boolean[N + 1];
      Queue<Node> q = new ArrayDeque<>();
      q.offer(new Node(from, 0));
      vst[from] = true;

      while (!q.isEmpty()) {
        Node n = q.poll();

        for (Node next : edge[n.a]) {
          if (vst[next.a]) {
            continue;
          }

          int nv = n.v + next.v;
          if (next.a == to) {
            sb.append(nv).append("\n");
            break;
          }

          vst[next.a] = true;
          q.offer(new Node(next.a, nv));
        }
      }
    }
    System.out.println(sb);
  }
}

 

 

풀이 2. 플로이드-워셜

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

class Main {

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int MAX = Integer.MAX_VALUE / 2;

    int[][] dis = new int[N + 1][N + 1];
    for (int i = 1; i <= N; i++) {
      Arrays.fill(dis[i], MAX);
      dis[i][i] = 0;
    }

    for (int i = 0; i < N - 1; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());

      dis[a][b] = dis[b][a] = v;
    }

    for (int k = 1; k <= N; k++) {
      for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
          dis[i][j] = Math.min(dis[i][k] + dis[k][j], dis[i][j]);
        }
      }
    }

    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      System.out.println(dis[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]);
    }
  }
}