[백준 1277] 발전소 설치 - JAVA

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

 

1번째 노드 -> N 번째 노드 (발전소) 의 최단경로(전선 길이)를 구하는 다익스트라 문제

 

모호한 조건, 조건을 무시해야 ac인 기이함, BFS로 비비기 시도가 겹쳐서 한 페이지 다 채울정도로 틀렸다.

https://www.acmicpc.net/board/view/156457

 

---

 

"연결된 발전소"의 처리가 중요하다.

 

연결된 발전소란, 현재 발전소에서 전선 길이 0으로 도달할 수 있으며, x/y좌표 값이 바뀜을 의미한다.

 

 

두 가지 탐색을 진행한다.

 

1. "연결된 발전소"에 대해 비용 갱신이 발생한다면, (현재 값)을 기록하고 pq에 넣는다.

2. "자신이 아닌 모든 발전소"에 대해 비용 갱신이 발생한다면, (현재 값 + 필요한 전선 길이)을 기록하고 pq에 넣는다.

 

1번 탐색 이후 2번 탐색에서 중복이 발생하므로, ac이후 해당 케이스를 제거해봤다. (connected arr)

오히려 탐색마다 방문 배열 만드는 비용때문에 시간이 더 늘었다. 고로 뺴도된다.

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

class Main {

  static class Node {

    int n, x, y;

    Node(int n, int x, int y) {
      this.n = n;
      this.x = x;
      this.y = y;
    }
  }

  static class Search implements Comparable<Search> {

    Node node;
    double v;

    Search(Node node, double v) {
      this.node = node;
      this.v = v;
    }

    @Override
    public int compareTo(Search o) {
      return Double.compare(this.v, o.v);
    }
  }

  static int N, W;
  static double M;
  static List<Node>[] conn;
  static Node[] dict;
  static double[] cost;
  static PriorityQueue<Search> pq = new PriorityQueue<>();

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

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

    N = Integer.parseInt(st.nextToken());
    W = Integer.parseInt(st.nextToken());
    M = Double.parseDouble(br.readLine());

    conn = new ArrayList[N + 1];
    dict = new Node[N + 1];

    for (int i = 1; i <= N; i++) {
      st = new StringTokenizer(br.readLine());
      conn[i] = new ArrayList<>();
      dict[i] = new Node(i, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

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

      conn[a].add(dict[b]);
      conn[b].add(dict[a]);
    }

    double INF = Double.MAX_VALUE / 2;
    int START = 1;
    int END = N;

    cost = new double[N + 1];
    Arrays.fill(cost, INF);
    cost[START] = 0;

    pq = new PriorityQueue<>();
    pq.offer(new Search(dict[START], 0));

    while (!pq.isEmpty()) {
      Search s = pq.poll();
      Node node = s.node;

      boolean[] connected = new boolean[N + 1];

      // 전선으로 연결된 발전소로 이동
      for (Node next : conn[node.n]) {
        if (cost[next.n] > s.v) {
          connected[next.n] = true;
          cost[next.n] = s.v;
          pq.offer(new Search(next, cost[next.n]));
        }
      }

      // 모든 발전소로 이동
      move(new Search(node, s.v), connected);
    }

    System.out.println((long) (cost[END] == INF ? -1 : cost[END] * 1000));
  }

  public static void move(Search s, boolean[] connected) {
    Node node = s.node;

    for (int i = 1; i <= N; i++) {
      Node next = dict[i];

      if (connected[i] || i == node.n) continue;
      
      double dis =
          Math.sqrt(
              Math.pow(Math.abs(node.x - next.x), 2) +
                  Math.pow(Math.abs(node.y - next.y), 2)
          );

      if (dis > M) continue;
      
      if (s.v + dis < cost[next.n]) {
        cost[next.n] = s.v + dis;
        pq.offer(new Search(dict[next.n], cost[next.n]));
      }
    }
  }
}