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

문제

1939번: 중량제한

풀이

이 문제에서는 간선과 가중치가 주어지며 이를 바탕으로 출발점(S)에서 목적점(E)까지 도달하면 된다.

한 가지 고려해야할 점은, 모든 노드를 탐색하게 되면 시간초과가 발생하기 때문에 이분탐색을 적용해야한다.

 

풀이 순서로는

1. 입력을 받으면서 가중치의 최댓값(r)을 찾아준다.

2. 이분탐색을 진행한다.

2-1. m(중간값)을 기준으로 dfs 탐색을 통해 목적지까지 유효한지 확인해본다.

2-2. 유효할 경우, l = m+1 유효하지 않을 경우 r = m-1

3. r 값 출력  

코드

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

public class Main {
    static int ans;
    static boolean[] v;
    static List<Node>[] list;

    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());

        list = new ArrayList[N+1];

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

        int l = 0, r = 0, m;
        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 d = Integer.parseInt(st.nextToken());

            list[a].add(new Node(b, d));
            list[b].add(new Node(a, d));

            r = Math.max(r, d);
        }

        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        while(r >= l){
            m = (l + r) / 2;

            ans = -1;
            v = new boolean[N+1];

            dfs(S, E, m);

            if(ans == -1) r = m - 1;
            else l = m + 1;
        }

        System.out.println(r);
    }

    private static void dfs(int cur, int end, int m) {
        if(cur == end){
            ans = cur;
            return;
        }

        v[cur] = true;

        for(Node next: list[cur]){
            if(v[next.n] || m > next.d) continue;

            dfs(next.n, end, m);
        }
    }

    static class Node{
        int n;
        long d;

        public Node(int n, long d){
            this.n = n;
            this.d = d;
        }
    }
}