[JAVA] BOJ 백준 1939번 - 중량제한

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1939번: 중량제한

---

2. 내가 푼 방법

특정 노드에서 특정 노드로 이동할 수 있는 다익스트라 알고리즘을 떠올렸다. 하지만 최대 가중치를 가지는 경로를 찾는다는 점에서 조금 변형된 문제이다.

 

시작 정점 s에서 다른 정점까지 갈 수 있는 최대 가중치를 dist 배열에 저장해 두었다. 이 최대 가중치들은 이동한 간선들의 최소 값을 특정하므로 현재까지의 가중치(w)와 이동하려는 정점의 가중치(tuple.w) 중에서 작은 값을 선택해야 한다.

public static void solution() {
    PriorityQueue<Tuple> queue = new PriorityQueue<>();
    queue.add(new Tuple(s, Integer.MAX_VALUE));

    int[] dist = new int[N+1];

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        int v = t.v;
        int w = t.w;

        if (dist[v] > w) continue;
        if (v == e) {
            result = Math.max(result, w);
            continue;
        }

        for (Tuple tuple : list[v]) {
            if (dist[tuple.v] < Math.min(w, tuple.w)) {
                dist[tuple.v] = Math.min(w, tuple.w);
                queue.add(new Tuple(tuple.v, dist[tuple.v]));
            }
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1939.java

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

class Main {
    static int N;
    static List<Tuple>[] list;
    static int s, e;
    static int result;

    public static void main(String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        PriorityQueue<Tuple> queue = new PriorityQueue<>();
        queue.add(new Tuple(s, Integer.MAX_VALUE));

        int[] dist = new int[N+1];

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int v = t.v;
            int w = t.w;

            if (dist[v] > w) continue;
            if (v == e) {
                result = Math.max(result, w);
                continue;
            }

            for (Tuple tuple : list[v]) {
                if (dist[tuple.v] < Math.min(w, tuple.w)) {
                    dist[tuple.v] = Math.min(w, tuple.w);
                    queue.add(new Tuple(tuple.v, dist[tuple.v]));
                }
            }
        }
    }

    public static class Tuple implements Comparable<Tuple> {
        int v;
        int w;

        public Tuple(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Tuple t) {
            return t.w - this.w;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        list = new ArrayList[N+1];

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[a].add(new Tuple(b, w));
            list[b].add(new Tuple(a, w));
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        br.close();
    }
}

---

4. 결과 및 회고

if 문에서 비교하는 대상들이 헷갈렸었는데,, 뇌를 장착하고 제대로 푸니까 바로 해결할 수 있었다.