[백준]1939: 중량제한 - JAVA

[백준]1939: 중량제한 - JAVA

www.acmicpc.net/problem/1939

1939번: 중량제한

 

풀이

이 문제는 이분탐색 문제이며 이전에 풀었던 프로그래머스의 징검다리 건너기 문제와 비슷했다. 

 

처음에는 인접행렬을 사용해서 풀었더니 메모리 초과가 났다. 그래서 다시 인접리스트로 바꾸어 풀어주었다. 이런 문제는 항상 인접행렬로 풀다보니 인접리스트르 바꾸는데 시간이 오래 걸렸다. 인접행렬은 N*N의 메모리 공간을 사용하므로 N에 큰 수가 들어오는 경우가 있다면 메모리 초과가 발생 할 것이다. 그러므로 이제는 인접 리스트로 풀도록 해야겠다.

 

BFS를 사용해 시작 노드부터 도착 노드까지의 경로 중에 최소값을 찾아 그 값이 현재 중량과 비교해 건널 수 있는지 확인해 주었다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int n, s, e;
    static ArrayList<Node> list[];
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        int m = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }
        
        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < m; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            int cost = scan.nextInt();    
            max = Math.max(cost, max);
            min = Math.min(cost, min);
            list[x].add(new Node(y, cost));
            list[y].add(new Node(x, cost));
        }
        
        s = scan.nextInt();
        e = scan.nextInt();
        int result = 0;
        while(min <= max) {
            int mid = (min + max) / 2;
            visited = new boolean[n + 1];
            
            if(bfs(mid)) { //s ~ e까지 mid의 중량이 건널 수 있는지 확인.
                min = mid + 1;
                result = mid;
            } else {
                max = mid - 1;
            }
        }
        System.out.println(result);
    }
    
    public static boolean bfs(int mid) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        visited[s] = true;
        
        while(!q.isEmpty()) {
            int temp = q.poll();
            
            if(temp == e) return true;
            
            for(int i = 0; i < list[temp].size(); i++) {
                if(list[temp].get(i).cost >= mid && visited[list[temp].get(i).n] == false) {
                    visited[list[temp].get(i).n] = true;
                    q.offer(list[temp].get(i).n);
                }
            }
        }
        return false;
    }
    
    public static class Node{
        int n;
        int cost;
        
        public Node(int n, int cost) {
            this.n = n;
            this.cost = cost;
        }
    }
}