1 분 소요

문제

문제 바로가기

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

접근방법

이분탐색과 BFS를 이용하여 풀 수 있는 문제다.

입력으로 주어지는 각 섬들의 연결 상태를 인접 리스트로 저장하고 중량의 최댓값을 구한다. 이분탐색을 통해 mid을 기준으로 bfs를 수행하여 mid의 중량으로 출발지에서 목적지까지 도달할 수 있는지 판별한다.

풀이

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

class Bridge {
    int end, weight;
    Bridge(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
}
public class Main {
    static int N, M;
    static List<Bridge>[] list;
    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());
        list = new ArrayList[N];

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

        int rw = 0;

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            int weight = Integer.parseInt(st.nextToken());
            list[start].add(new Bridge(end, weight));
            list[end].add(new Bridge(start, weight));
            rw = Math.max(rw, weight);
        }

        st = new StringTokenizer(br.readLine());
        int left = Integer.parseInt(st.nextToken()) - 1;
        int right = Integer.parseInt(st.nextToken()) - 1;

        int lw = 0;
        int res = 0;

        while(lw <= rw) {
            int mid = (lw + rw) / 2;
            if(bfs(left, right, mid)) {
                res = mid;
                lw = mid + 1;
            }
            else {
                rw = mid - 1;
            }
        }

        bw.write(res+"");
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean bfs(int left, int right, int weight) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] check = new boolean[N];
        q.offer(left);
        check[left] = true;
        while(!q.isEmpty()) {
            int temp = q.poll();
            if(temp == right)
                return true;
            for(int i = 0; i < list[temp].size(); i++) {
                Bridge bridge = list[temp].get(i);
                if(!check[bridge.end]) {
                    if (bridge.weight >= weight) {
                        q.offer(bridge.end);
                        check[bridge.end] = true;
                    }
                }
            }
        }

        return false;
    }
}

댓글남기기

참고