이번에 풀어본 문제는
백준 1939번 중량제한 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Bridge
{
    int n,weight;

    public Bridge(int n, int weight) {
        this.n = n;
        this.weight = weight;
    }
}
public class Main {
    static List<List<Bridge>> map;
    static int from,to;
    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());

        map = new ArrayList<>();
        for(int i = 0; i <= n; ++i) map.add(new ArrayList<>());

        int start = Integer.MAX_VALUE;
        int end = Integer.MIN_VALUE;
        for(int i = 0; i < m; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int fst = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            if(weight < start) start = weight;
            if(weight > end) end = weight;

            map.get(fst).add(new Bridge(sec,weight));
            map.get(sec).add(new Bridge(fst,weight));
        }

        st = new StringTokenizer(br.readLine());
        from = Integer.parseInt(st.nextToken());
        to = Integer.parseInt(st.nextToken());

        int answer = 0;
        boolean [] visited;
        while(start <= end)
        {
            Queue<Integer> q = new LinkedList<>();
            visited = new boolean[n+1];
            visited[from] = true;
            q.add(from);
            int mid = (start + end) / 2;
            boolean canMove = false;
            while(!q.isEmpty())
            {
                int cur = q.poll();
                if(cur == to)
                {
                    canMove = true;
                    answer = Math.max(answer,mid);
                    break;
                }
                for(Bridge next : map.get(cur))
                {
                    if(visited[next.n] || mid > next.weight) continue;
                    visited[next.n] = true;
                    q.add(next.n);
                }
            }
            if(canMove) start = mid+1;
            else end = mid-1;
        }
        System.out.print(answer);
    }
}

📝 풀이

N개의 섬이 존재하는 나라에 A와 B섬을 연결하는 C중량을 버틸 수 있는 다리가 M개 입력값으로 주어집니다. 공장을 가진 두 섬이 주어졌을 때, 해당 그래프에서 공장에서 공장으로 한번의 이동으로 옮길 수 있는 중량의 최댓값을 구하는 문제입니다.
숫자의 범위가 크기 때문에 이분탐색을 활용했습니다.
먼저, 다리의 정보를 입력 받을 때, 최소/최댓값을 각각 start/end로 담아두었습니다. 입력값의 최소/최댓값으로 첫 mid값을 설정하고, 그 값을 기준으로 탐색을 시작합니다. 탐색은 from 섬부터 시작하며 bfs 탐색을 진행하는 중 to 섬을 만나게 되면, 해당 mid중량으로는 가능하다고 판단하여 값을 증가시킬 수 있습니다. 모든 반복을 마쳤을 때, to섬까지 도달했던 가장 큰 mid값을 결과로 출력해주면 해결할 수 있습니다.

📜 후기

사실 먼저 출발한 경로가 앞서 방문배열을 true로 변경해버리면, 가능한 다른 경로의 탐색을 진행하지 못할 것 같아서 틀리면 dfs로 바꿔보려 했으나 의외로 정답이 맞게 나와서 그냥 제출하게 되었습니다. 지금은 현재 풀이로 생각이 너무 굳어져 있어, 내일 다른 시선으로 다시 한번 훑어볼 생각입니다.