[백준] 1939. 중량제한

문제 링크

[백준] 1939. 중량제한

풀이 과정

시간 제한으로 인해 모든 간선의 비용, 즉 중량을 정해두고 초과하는 지를 확인하면서 그래프 탐색을 할 수 없기에 그래프 탐색에 이분 탐색을 적용해야 하는 문제입니다. 중량 제한을 초과하면 안되므로, mid 라는 중량 기준을 정해둡니다. 이 값 이상으로 BFS 탐색이 가능하다면, 중량을 더 올려 확인해봅니다.

int low = 0, high = 1_000_000_000;

while (low <= high) {
    int mid = (low + high) / 2;

    if (bfs(mid)) {
        low = mid + 1;
        answer = mid;
    } else high = mid - 1;
}

초기 high 값을 문제에서 주어진 중량 제한 C의 최대 범위 10,000,000으로 설정한 뒤 이분탐색을 진행합니다.

mid 값으로 목적지까지 BFS 탐색이 가능하면 low 값을 더 올려 중량 제한 범위를 높이고, 불가능하다면 high 값을 내려 중량 제한 범위를 낮춥니다.

static boolean bfs(int mid) {
    Arrays.fill(visit, false);
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visit[start] = true;

    while (!queue.isEmpty()) {
        int now = queue.poll();

        if (now == dest) return true;

        for (Edge next : adj[now]) {
            if (!visit[next.vertex] && next.cost >= mid) {
                visit[next.vertex] = true;
                queue.add(next.vertex);
            }
        }
    }

    return false;
}

bfs 메소드 는 비용이 mid 이상인 간선들만 사용하여 시작점으로부터 도착지까지 BFS 탐색이 가능하면 true 를, 불가능하다면 false 를 리턴합니다.

코드

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

public class Main {
    static int N, M;
    static int start, dest;
    static ArrayList<Edge>[] adj;
    static boolean[] visit;
    static int answer;

    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());
        adj = new ArrayList[N + 1];
        visit = new boolean[N + 1];

        for (int i = 1; i <= N; i++) adj[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 C = Integer.parseInt(st.nextToken());

            adj[A].add(new Edge(B, C));
            adj[B].add(new Edge(A, C));
        }

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        dest = Integer.parseInt(st.nextToken());

        int low = 0, high = 1_000_000_000;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (bfs(mid)) {
                low = mid + 1;
                answer = mid;
            } else high = mid - 1;
        }

        System.out.println(answer);
    }

    static boolean bfs(int mid) {
        Arrays.fill(visit, false);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visit[start] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();

            if (now == dest) return true;

            for (Edge next : adj[now]) {
                if (!visit[next.vertex] && next.cost >= mid) {
                    visit[next.vertex] = true;
                    queue.add(next.vertex);
                }
            }
        }

        return false;
    }

    static class Edge {
        int vertex;
        int cost;

        public Edge(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }
    }
}