[백준] 1939번 중량제한

문제 설명

https://www.acmicpc.net/problem/1939

문제 풀이

• 우선 BFS를 이용해 풀이해 보았다.
  - 방문탐색으로 해당 노드에 방문할 수 있는 최대 중량 보다 작으면 진입 막음.
  - 해당 방식을 이용하면 메모리 초과 및 시간 초과가 발생한다.
• 이분 탐색으로 무게를 제한하고 해당 무게에 대해 BFS로 가능 여부를 판별하여 풀이하였다.

소스 코드 (JAVA)

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

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static int N, M, S, E, maxW = 0;
    public static ArrayList<Point>[] map;

    public static class Point {
        int cur, w;
        public Point (int cur, int w) {
           this.cur = cur;
           this.w = w;
        }
    }

    public static boolean isValid(int limit) {
        Queue<Integer> q = new ArrayDeque<>();
        int[] chk = new int[N+1];
        q.add(S);
        chk[S] = 1;
        while(!q.isEmpty()) {
            int cur = q.poll();
            if (cur == E) return true;
            for (int i = 0; i < map[cur].size(); i++) {
                int node = map[cur].get(i).cur;
                int w = map[cur].get(i).w;
                if (chk[node] == 1 || w < limit) continue;
                chk[node] = 1;
                q.add(node);
            }
        }
        return false;
    }

    public static int solve() {
        int lo = 1;
        int hi = maxW + 1;
        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (isValid(mid)) lo = mid;
            else hi = mid;
        }
        return lo;
    }

    //입력
    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new ArrayList[N+1];
        for (int i = 1; i <= N; i++)
            map[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());
            maxW = Math.max(maxW, c);
            map[a].add(new Point(b, c));
            map[b].add(new Point(a, c));
        }
        st = new StringTokenizer(br.readLine(), " ");
        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
    }

    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out)) ;
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        bw.write(solve() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}