[백준] 1939. 중량제한 (Java)

 

1939번: 중량제한

풀이

일단 이 문제는 다익스트라가 맞다. 틀려서 결국 구글링을 하긴 했는데 대부분 이분탐색과 BFS를 조합하여 했지만 이분탐색으로 풀면 뭔가 문제의 취지에 안맞는 느낌(?)이 들어서 다익스트라 코드도 찾아봤다.

 

다익스트라로 풀 경우

• 우선순위큐를 사용하여 중량 기준 내림차순으로 들어가도록 한다.
• 일반적인 최단경로 찾기의 경우 시작노드 기준 거리 정보를 업데이트를 하는 dist[]을 두는데, 여기선 해당 위치로 보낼 수 있는 최대 중량 제한값을 저장한다.
• 큐에서 뽑은게 from, from에서 갈 수 있는 후보들이 to라고 하면
  • 가려는 위치 dist[to]에 dist[to]보다 더 큰 값이 들어올 때만 dist[to]를 업데이트 한다.
  • 이때 중량은 큐에서 뽑은 from의 weight와 to의 weight 둘 중 작은 값으로 해야 한다.

 

코드

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

public class Main {
    static int N, M, A, B;
    static int[] dist;
    static ArrayList<Node> node[];
    static final int INF = 1000000001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dist = new int[N + 1];
        Arrays.fill(dist, -1);
        node = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++)
            node[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());
            node[from].add(new Node(to, weight));
            node[to].add(new Node(from, weight));
        }
        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        Dijkstra();

        bw.write(String.valueOf(dist[B]));
        br.close();
        bw.close();
    }

    public static void Dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> (o2.weight - o1.weight));
        pq.offer(new Node(A, INF));
        dist[A] = INF;
        while (!pq.isEmpty()) {
            int from = pq.peek().to;
            int weight = pq.peek().weight;
            pq.poll();
            if (dist[from] > weight) continue; // 이미 중량이 크면 update할 필요가 없으므로

            for (int i = 0; i < node[from].size(); i++) {
                int to = node[from].get(i).to;
                int weightTo = Math.min(weight, node[from].get(i).weight);
                if (weightTo > dist[to]) {
                    dist[to] = weightTo;
                    pq.offer(new Node(to, weightTo));
                }
            }
        }
    }

    static class Node {
        int to;
        int weight;

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

 

 

---

 

이분탐색, BFS로 풀 경우

• 이분탐색의 시작값 (start)은 0이다.
• 처음에 노드별 중량을 입력받을 때 최대 중량이 이분탐색의 끝값 (end)이 된다.
• 중간값을 기준으로 시작점에서 끝점까지 갈 수 있는지 BFS탐색을 한다.
  • 이때 입력받은 중간값보다 중량이 작거나 같아야 하는데
  • 끝점까지 도달에 성공하면 start = mid + 1
  • 실패하면 end = mid - 1로
  • 중간값을 조절하면서 최댓값이 되는 값을 찾아나간다.

 

코드

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

public class Main {
    static int N, M, A, B, start, end;
    static ArrayList<Node> node[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        node = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++)
            node[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());
            node[from].add(new Node(to, weight));
            node[to].add(new Node(from, weight));
            end = Math.max(end, weight);
        }
        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        while (start <= end) {
            int mid = (start + end) / 2;
            if (BFS(mid)) start = mid + 1;
            else end = mid - 1;
        }
        bw.write(String.valueOf(end));
        br.close();
        bw.close();
    }

    public static boolean BFS(int limit) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        q.offer(A);
        visited[A] = true;

        while (!q.isEmpty()) {
            int front = q.poll();
            if (front == B) return true;

            for (int i = 0; i < node[front].size(); i++) {
                int to = node[front].get(i).to;
                int weight = node[front].get(i).weight;
                if (visited[to] || weight < limit) continue;
                visited[to] = true;
                q.offer(to);
            }

        }
        return false;
    }

    static class Node {
        int to;
        int weight;

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