백준 22116 - 창영이와 퇴근

문제

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

리뷰

크루스칼을 이용하여 풀이할 수 있는 문제였다. 우선 1차원 parent 배열을
활용하기 위해 좌표 x, y를 N*y+x 수식을 통하여 인덱스로 매핑하고
parent를 N*N사이즈로 선언하였다.

이후 한 좌표에서 가능한 상하좌우 네방향을 간선으로 설정하여 비용 기준
최소힙에 넣어주고 크루스칼 로직에서 1,1에서 N-1, N-1 까지의 MST가
형성될 때까지 간선을 채택하며 가장 큰 간선 비용을 도출하여 답을 구했다.

문제를 풀며 유의할 점은 $N=1$일 때 생성될 수 있는 간선이 없어 답이 무조건
0이 되는 케이스를 처리해주어야 한다는 것이었다.

로직의 시간복잡도는 간선의 개수 $M=4 \times N \times N$일때 크루스칼 로직의
$O(MlogM)$으로 수렴하며 $N=1,000$인 최악의 경우에도 제한 조건 2초를
무난히 통과한다.

코드

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.MIN_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[] parent;
    static int[][] map;
    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));
        N = parseInt(br.readLine());
        map = new int[N][N];
        parent = new int[N * N];

        if(N==1){
            System.out.println(0);
            return;
        }

        StringTokenizer st;

        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < N; x++) {
                map[y][x] = parseInt(st.nextToken());
            }
        }

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};


        /**
         * 한 좌표에서 상하좌우 네방향으로 가능한 경우를
         * 간선(Edge)로 생성하여 최소힙에 저장한다.
         */
        int nx, ny, u, v, w;
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                u = convert(x, y);

                for (int i = 0; i < dx.length; i++) {
                    nx = x + dx[i];
                    ny = y + dy[i];

                    if (isOut(nx, ny))
                        continue;

                    v = convert(nx, ny);
                    w = calcSlope(map[y][x], map[ny][nx]);
                    pq.offer(new Edge(u, v, w));
                }
            }
        }

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

    static int convert(int x, int y) {
        return N * y + x;
    }

    static boolean isOut(int x, int y) {
        return x < 0 || x >= N || y < 0 || y >= N;
    }

    static int calcSlope(int h1, int h2) {
        return Math.abs(h1 - h2);
    }

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

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

    /**
     * 정점의 개수 N^2
     * 간선의 개수 M = 4*N^2(유효하지 않은 인덱스 제외하면 그이하)
     *
     * 크루스칼의 시간복잡도 O(M log M)
     */

    static int kruskal() {
        Arrays.fill(parent, -1);
        int maxSlope = MIN_VALUE;

        while (true) {
            Edge e = pq.poll();
            int r1 = find(e.u);
            int r2 = find(e.v);

            if (r1 == r2) continue;

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

            maxSlope = Math.max(maxSlope, e.w);
            if (find(convert(0, 0)) == find(convert(N - 1, N - 1)))
                break;
        }

        return maxSlope;
    }

    static class Edge {
        int u, v, w;

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

결과