백준 27945 - 슬슬 가지를 먹지 않으면 죽는다

문제

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

리뷰

크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.

주어진 문제에선 노점이 여는 날($t_i$)가 간선의 가중치로 주어지는데 이 가중치가
날짜($d$)를 넘지 않는 선에서 최대의 $d$를 구하는 것이 관건이었다.

이에 따라 크루스칼 로직내 간선을 채택하는 while문에서 간선의 가중치가 day를
초과할 경우 break하는 조건문을 추가하여 답을 도출하도록 구현하였다.
day를 필자의 로직에서는 0부터 시작하도록 구하였기 때문에 이에 따라 day+1을
노점이 여는 날(가중치)와 비교하도록 설정하였다.

로직의 시간복잡도는 크루스칼의 $O(NlogM)$으로 수렴하고 이는 $N=10^5$,
$M=4\times 10^4$인 최악의 경우에도 제한 조건 1초를 무난히 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        parent = new int[N + 1];

        int u, v, w;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = parseInt(st.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        System.out.println(kruskal(N));
        br.close();
    }

    static int kruskal(int N) {
        Arrays.fill(parent, -1);
        int day = 0;

        while (!pq.isEmpty() && day < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) continue;

            if (day + 1 < e.w) break;
            day++;
        }

        return day + 1;
    }

    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return false;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }

        return true;
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과