백준 11085 (군사 이동) -java

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

11085번: 군사 이동

 

문제

전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 이에 비례하는 수의 군사가 지나갈 수 있습니다.

Baekjoon World의 국왕은 군사들이 뭉치는 것이 유리하다고 생각해서, 미리 Cube World로 가는 경로를 정해 두고 그 경로로만 모든 군사를 보냈습니다. Baekjoon World의 국왕은 총명해서, 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택했습니다.

그런데 전쟁 때문에 어느 길로 보냈는지에 대한 기록이 불타 없어져 버렸습니다. 전쟁사를 완성하려면 이 기록이 꼭 필요합니다. 위대한 과학자인 당신이 다시 복구해 주세요.

 

유형 : 다익스트라 or Union - Find

 

접근 방식

• 출발지에서 목적지까지 경로 중 가장 작은 값이 최대 값이 되도록 해야 한다.
• 현재 간선의 값과 현재까지 지나온 경로에서 가장 작은 값을 비교하여 해당 값을 지점의 최댓값이 되도록 탐색한다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int s = 0;

    static int e = 0;

    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(bf.readLine(), " ");

        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];

        for(int i=0;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[x].add(new Node(y,v));
            graph[y].add(new Node(x,v));
        }

        go();

        bf.close();
    }

    static void go(){

        int[] dis = new int[n+1];

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> y.c - x.c
        );

        pq.add(new Node(s,1001));

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            for(Node next : graph[cur.v]){

                int curV = Math.min(cur.c,next.c);

                if(dis[next.v] < curV){
                    dis[next.v] = curV;
                    pq.add(new Node(next.v,curV));
                }
            }
        }

        System.out.println(dis[e]);

    }

}
class Node{
    int v;
    int c;

    Node(int v,int c){
        this.v = v;
        this.c = c;
    }
}