ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

Algorithm/Baekjoon

[Java] ๋ฐฑ์ค€ 1939๋ฒˆ - ์ค‘๋Ÿ‰์ œํ•œ

๊ฐœ๋ฐœ๊ฐœ๊ตด๐Ÿธ 2022. 6. 13. 21:14

[๋ฌธ์ œ]

 

[ํ’€์ด]

์ด์ค‘ํƒ์ƒ‰ + BFS๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฌธ์ œ๋กœ ์•„๋ž˜์˜ ๋ธ”๋กœ๊ทธ๋ฅผ ์ฐธ๊ณ ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

https://hidelookit.tistory.com/200

 

[๋ฐฑ์ค€ 1939] ์ค‘๋Ÿ‰์ œํ•œ (์ž๋ฐ”)

๋ฐฑ์ค€ 1939๋ฒˆ ์ค‘๋Ÿ‰์ œํ•œ (์ž๋ฐ”) ์ถœ์ฒ˜ www.acmicpc.net/problem/1939 1939๋ฒˆ: ์ค‘๋Ÿ‰์ œํ•œ ์ฒซ์งธ ์ค„์— N, M(1≤M≤100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๋‹ค๋ฆฌ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์„ธ ์ •์ˆ˜ A, B(1≤A, B≤N), C(1≤..

hidelookit.tistory.com

 

left์— ์ตœ์†Œ๊ฐ’ 0์„ ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.

right ์— ๋‹ค๋ฆฌ๋“ค์ค‘ ๊ฐ€์žฅ ์ค‘๋Ÿ‰์ด ํฐ๊ฐ’์„ ๋„ฃ์–ด์ค๋‹ˆ๋‹ค.

 

(left + right)/2์ธ mid ๊ฐ’๋ถ€ํ„ฐ ํ•ด๋‹น ์ค‘๋Ÿ‰์˜ ์ง์œผ๋กœ ์„ฌ-์„ฌ์„ ์ด๋™ํ• ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋ฉฐ,

๋งŒ์•ฝ ์ด๋™ํ• ์ˆ˜ ์žˆ๋‹ค๋ฉด mid+1, ์ด๋™ํ• ์ˆ˜์—†๋‹ค๋ฉด mid-1ํ•˜๋ฉฐ ์ตœ๋Œ€ ์ค‘๋Ÿ‰์„ ์ฐพ์Šต๋‹ˆ๋‹ค.

 

[์ฝ”๋“œ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// ํ•œ ๋ฒˆ์˜ ์ด๋™์—์„œ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ๋Š” ๋ฌผํ’ˆ๋“ค์˜ ์ค‘๋Ÿ‰์˜ ์ตœ๋Œ“๊ฐ’

class Bridge{
    int island;
    int weight;
    public Bridge(int island, int weight) {
        this.island = island;
        this.weight = weight;
    }
}

public class Main {
    public static int N;
    public static int M;
    public static ArrayList<ArrayList<Bridge>> bridge = new ArrayList<>();
    public static int max = 0;
    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());
        M = Integer.parseInt(st.nextToken());

        for(int i=0;i<=N;i++) {
            bridge.add(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 c = Integer.parseInt(st.nextToken());
            // ์–‘๋ฑกํ–ฅ์ด๋ผ 2๊ฐœ ๋„ฃ์–ด์คŒ
            bridge.get(a).add(new Bridge(b,c));
            bridge.get(b).add(new Bridge(a,c));

            if(max < c) {
                max = c;
            }
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int left = 0;
        int right = max;

        while(left <= right) {
            int mid = (left + right)/2;
            if(bfs(start,end,mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
    public static boolean bfs(int start, int end, int mid) {
        boolean[] visit = new boolean[N+1];
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visit[start] = true;

        while(!q.isEmpty()) {
            int p = q.poll();

            if(p == end) {
                return true;
            }

            for(Bridge i: bridge.get(p)) {
                if(!visit[i.island] && mid <= i.weight) {
                    visit[i.island] = true;
                    q.add(i.island);
                }
            }
        }
        return false;
    }
}