[백준 - 27945][GOLD 3][해설 X] - 슬슬 가지를 먹지 않으면 죽는다 (JAVA)

 

문제 링크

---

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

 

문제

---

키위새는 가지와 사랑에 빠지면서 가지로 맛있는 요리를 하기 위해 1번부터 N번까지의 번호가 붙은 N개의 요리 학원에 다니기 시작했다.

각 요리 학원 사이에는 총 M개의 양방향 길이 있고, i번째 길에는 정확히 𝑡𝑖일에만 문을 여는 가지 디저트 노점이 있다. (𝑡𝑖는 모두 다르다.) 아직 가지 요리를 배우는 중인 키위새는 직접 가지 요리를 해 먹지는 못하다 보니 가지 부족증(hypomelitzemia)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저트를 먹지 않으면 쓰러지게 된다. 심지어 기억력도 퇴화해 N-1개의 길만을 기억할 수 있게 되었다!

모든 요리 학원에 다닐 수 있도록 𝑁−1개의 길을 골랐을 때, 키위새가 쓰러지는 날이 d일차라고 하자. 날짜가 1일차부터 시작할 때, d의 최댓값을 구해보자.

 

입력

---

첫째 줄에 요리 학원의 수 N, 길의 수 M이 주어진다. (2≤𝑁≤105; 𝑁−1≤𝑀≤min(5×10^5) 

둘째 줄부터 M개 줄에 각 길이 연결하는 두 학원의 번호 𝑢𝑖, 𝑣𝑖, 길에 있는 노점이 여는 날 𝑡𝑖가 주어진다. (1≤𝑢𝑖,𝑣𝑖≤𝑁; 𝑢𝑖≠𝑣𝑖; 𝑡𝑖≠𝑡𝑗)

각 요리 학원에서 길을 따라 모든 요리 학원으로 가는 방법이 존재하는 경우만 주어진다.

두 요리 학원 사이를 곧바로 잇는 길은 많아야 하나이다.

 

출력

---

첫째 줄에 d의 최댓값을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Restaurant> restaurantList = new ArrayList<>();

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int day = Integer.parseInt(st.nextToken());

            Restaurant restaurant = new Restaurant(start,end,day);

            restaurantList.add(restaurant);
        }
        
        //노점이 빨리 여는 순서부터 정렬
        Collections.sort(restaurantList);

        parent = new int[N+1];

        for(int i=0;i<parent.length;i++){
            parent[i] = i;
        }

        Set<Integer> graph[] = new HashSet[N+1];

        for(int i=0;i<graph.length;i++){
            graph[i] = new HashSet<>();
        }

        //가능한 한번도 끊기지 않고 연속적으로 노점을 가야하므로 빨리 여는 노점부터 선택
        for(Restaurant restaurant : restaurantList){
            int pa = getParent(restaurant.start);
            int pb = getParent(restaurant.end);

            if(pa != pb){
                graph[restaurant.start].add(restaurant.end);
                graph[restaurant.end].add(restaurant.start);

                union(pa,pb);
            }
        }

        int day = 1;
        
        //n일차 노점이 있는 경로가 있는지 확인 찾기
        for(Restaurant restaurant : restaurantList){
            //현재 날짜의 노점이 아니라면 키위는 쓰러진다.
            if(restaurant.day != day){
                break;
            }
            //n일차 노점을 갈 수 없으면 키위는 쓰러진다.
            if(!graph[restaurant.start].contains(restaurant.end)){
               break;
            }
            day++;
        }

        System.out.println(day);
    }

    public static int getParent(int curr){
        if(parent[curr] == curr){
            return curr;
        }

        parent[curr] = getParent(parent[curr]);

        return parent[curr];
    }

    public static void union(int a, int b){
        int pa = getParent(a);
        int pb = getParent(b);

        if(pa < pb){
            parent[a] = b;
        }else{
            parent[b] = a;
        }
    }
}

class Restaurant implements Comparable<Restaurant>{
    int start;
    int end;
    int day;

    public Restaurant(int start, int end, int day){
        this.start = start;
        this.end = end;
        this.day = day;
    }

    @Override
    public int compareTo(Restaurant o) {
        return this.day - o.day;
    }
}

 

 

실행 결과

---

 

팁

---

• 경로를 확인하는데 Set을 이용한 그래프를 이용하면 O(1)의 속도로 빠르게 찾을 수 있다.