백준 1800번: 인터넷 설치 (Java)

접근

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

1800번: 인터넷 설치

dfs가 먼저 떠올랐지만 방문 처리 조건과 같은 세세한 내용이 떠오르지 않아 힌트를 확인하고 풀었다.
그래프 이론/이분 탐색/다익스트라/매개 변수 탐색 이라는 힌트를 받고 문제를 해결할 수 있었다.

핵심은

1. 임의의 수 x보다 클 경우 경로의 가중치를 1로 놓고, 그렇지 않을 경우 가중치를 0으로 놓는 다익스트라 함수를 설정한다. 이 함수를 이용하여 N번 노드에 도달한 경로들 중, 가중치의 합이 가장 작은 값을 얻을 수 있다. 이 값은 N번 노드에 도착한 경로들 중 x보다 비용이 큰 경로들의 개수를 의미하며, 이 값이 K값보다 작은지를 결과로 리턴한다.
2. 경로들의 코스트 구간을 이분탐색을 통해 위의 다익스트라 함수가 true 를 리턴하는 가장 작은 mid 값을 구하면 문제의 해답이다.

이분 탐색을 통해 구해진 답이 a라고 할 때, N에 도달한 경로에서 a보다 큰 비용을 가진 경로들의 개수가 K개이기 때문에 코레스코로부터 할인을 받을 수 있고, 그로 인하여 남은 경로들 중 가장 큰 값이 a 가 되는 것이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static class Pair implements Comparable<Pair> {

    private int index, cost;

    public Pair(int index, int cost) {
      this.index = index;
      this.cost = cost;
    }

    @Override
    public int compareTo(Pair o) {
      return this.cost - o.cost;
    }
  }

  static int N, P, K;
  static ArrayList<Pair>[] map;
  static int[] dist;

  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());
    P = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    dist = new int[N + 1];
    map = new ArrayList[N + 1];
    for (int t = 1; t <= N; t++) {
      map[t] = new ArrayList<>();
    }

    int max = 0;
    int a, b, c;
    for (int t = 0; t < P; t++) {
      st = new StringTokenizer(br.readLine());
      a = Integer.parseInt(st.nextToken());
      b = Integer.parseInt(st.nextToken());
      c = Integer.parseInt(st.nextToken());
      map[a].add(new Pair(b, c));
      map[b].add(new Pair(a, c));
      max = Math.max(max, c);
    }
    br.close();

    int start = 0;
    int ans = Integer.MAX_VALUE;
    while (start <= max) {
      int mid = (start + max) / 2;
      if (dijstra(mid)) {
        ans = mid;
        max = mid - 1;
      } else {
        start = mid + 1;
      }
    }

    if (ans == Integer.MAX_VALUE) {
      ans = -1;
    }
    System.out.println(ans);
  }

  static boolean dijstra(int x) {
    PriorityQueue<Pair> queue = new PriorityQueue<>();
    Arrays.fill(dist, Integer.MAX_VALUE);

    dist[1] = 0;
    queue.add(new Pair(1, 0));

    while (!queue.isEmpty()) {
      Pair tmp = queue.poll();
      int now = tmp.index;
      int cost = tmp.cost;

      if (dist[now] < cost) continue;

      for (Pair n : map[now]) {
        int next = n.index;
        int nextCost = cost;
        if (n.cost > x) {
          nextCost++;
        }
        if (nextCost < dist[next]) {
          dist[next] = nextCost;
          queue.add(new Pair(next, nextCost));
        }
      }
    }
    return dist[N] <= K;
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!