백준 1939번 - 중량제한 / Java

문제

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

1939번: 중량제한

푸는데 2시간 반 걸린 문제.

일단 이분 탐색이랑 BFS가 섞여있는 문제라 1차적으로 난해했는데 거기서 또 중복된 간선 때문에 시간 초과가 나서 멘붕이 왔다

일단 이분 탐색으로 가능한 무게의 최댓값을 잡아 놓은 뒤에 BFS를 실시해서 해당 정점으로 이동할 수 있는지 검사하면 된다.

정점이 최대 10000개라 인접 행렬로 구현하면 10000*10000이라 메모리가 터진다. 따라서 인접 리스트로 구현해야 된다

그리고 간선의 개수가 100000개라 우선순위 큐를 사용해야 시간 안에 통과가 된다.

 

 

알고리즘

1.  1부터 최대 무게까지 이분 탐색을 실시해서 테스트할 무게를 정한다

2. BFS로 간선을 탐색한다. 최대 무게보다 간선의 무게가 낮으면 탐색하지 않는다. 목적지에 도착할 수 있으면 무게를 저장한다

3. 저장된 무게 중 최댓값을 출력한다

소스코드

/*
 * BOJ1939
 * 2020.02.05
 * Hyeonseong 
 */
import java.util.*;    
public class BOJ1939 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Node implements Comparable<Node>{
    int spot; // 연결된 정점
    int gram; // 중량
    Node(int spot, int gram){
        this.spot = spot;
        this.gram = gram;
    }
    @Override
    public int compareTo(Node o) {
        return o.gram - this.gram;
    }
}
class Solution{
    int n; // 정점 정보
    int m; // 간선 정보
    int r,c; // 정답
    int maxWeight;
    ArrayList<Node> map[];
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        map = new ArrayList[10001];
        for(int i=0;i<10001;i++) {
            map[i] = new ArrayList<Node>();
        }
        for(int i=0;i<m;i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            map[a].add(new Node(b,c));
            map[b].add(new Node(a,c));
            if(maxWeight < c) {
                maxWeight = c;
            }
        }
        r = scan.nextInt();
        c = scan.nextInt();
        binary();
    }
    public void binary() {
        int max = 0;
        int start = 1;
        int end = maxWeight;
        while(start<=end) {
            int mid = (start+end)/2;
            if(bfs(mid)) { // 해당무게로 BFS실시
                if(max < mid) {
                    max = mid;
                }
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
        System.out.println(max);
    }
    public boolean bfs(int maxGram) {
        boolean visit[] = new boolean[10001];
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        for(int i=0;i<map[r].size();i++){
            if(map[r].get(i).gram>=maxGram) {
                q.offer(map[r].get(i));
                visit[map[r].get(i).spot] = true;
            }
        }
        while(!q.isEmpty()) {
            Node t = q.poll(); // 우선수위 큐를 사용해서 중복된 간선중 최대중량을 가진 간선을 뽑는다
            int x = t.spot;
            if(x==c) {
                return true;
            }
            if(t.gram<maxGram) continue;
            for(int i=0;i<map[x].size();i++) {
                Node t2 = map[x].get(i);
                if(t2.gram>=maxGram && !visit[t2.spot]) {
                    q.offer(t2);
                    visit[t2.spot] = true;
                }
            }
        }
        return false;
    }
}