[백준 / BOJ] 17472번 : 다리 만들기 2 - JAVA

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

[17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net](https://www.acmicpc.net/problem/17472)

섬 구분하기

일단은 각 섬을 구분하기 위해 init_land 함수를 구현했다. 섬을 구분하도록 하는 변수 group을 2로 두고, BFS로 근처 땅을 모두 group으로 초기화하도록 했다. 섬 하나에 속한 땅을 모두 group으로 바꾼 후에는 1 증가하고 다음 땅을 찾는다.

즉, init_land 이후 map에는 2부터 group - 1번까지의 섬이 존재하게 된다.

섬을 잇는 모든 다리 구하기

bridge 함수를 통해 "모든 다리" 를 구한다. 이 중 어떤 다리를 사용할 것인지는 다음 함수에서 우선순위 큐를 사용하여 결정할 것이다.

map[i][j]가 0이 아니라면 상하좌우 4방향으로 쭉 이동한다.
 - map 범위를 벗어나면 break한다.
 - 만일 map[i][j]와 같은 번호의 땅이 나오면 break한다.
 - map[i][j]과 번호가 다르고, 바다가 아닌 땅이 나오면 두 땅의 번호와 걸린 시간을 우선순위 큐에 저장한다.
    - 단, 걸린 시간이 2 미만인 경우에는 break한다.

 

다리 선택하기 Union-Find

앞선 함수에서는 가능한 모든 다리를 모았기 때문에, 이 중 가장 작은 값으로 모든 섬을 잇도록 해야 한다. 이를 위해 다리 길이를 기준으로 하는 우선순위 큐에 모든 다리를 넣어놓은 것이다.

 

그럼 "어떤 섬을 이어야할지"가 남는다. 기준이 다리 길이이기 때문에, 기존에 이어져 있던 섬들을 대상으로 한 원소가 더 있을 수도 있다. 이 부분을 해결하기 위해 Union-Find를 사용했다.

 

우선순위 큐에서 원소를 poll한다. 해당 원소는 [섬1의 번호, 섬2의 번호, 다리의 길이]로 구성되어 있으므로, 섬1과 섬2를 union해준다. 이 때 만일 두 섬이 이미 이어진 상태라면 union(섬1, 섬2)의 리턴값이 0이다. 새로 union한 경우에는 다리의 길이를 total에 더해주고, 만일 이번 rank의 값이 group - 2와 같다면 모든 섬이 다 이어진 것이므로 함수를 리턴한다. (group - 2인 이유는 섬 번호를 2번부터 시작했기 때문이다.)

 

모든 섬이 다 이어졌는가?

섬을 잇는 작업이 끝난 후에 한 번 더 확인해주어야 할 게 있다. 만일 가능한 다리를 다 사용했는데도 이어지지 않은 섬이 있다면 -1을 리턴해야 하기 때문이다. 이는 rank 값을 보고 확인할 수 있다.

 

union 함수에서 rank가 자식의 rank값을 계속 더해주어 부모 노드의 rank 값이 자신의 모든 자녀 노드의 개수를 나타내도록 했다. 따라서 rank[find(2)]가 group - 2와 같다면, 모든 섬이 이어진 것이다. 만일 그보다 작다면 이어지지 못한 섬이 존재하고, -1을 리턴해야 한다.

 

전체 코드

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

// 시간 : 80ms
// 메모리 : 11740KB
public class Main {

    static int N;
    static int M;
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,-1,0,1};
    static int[] parent;
    static int[] rank;
    static int total;
    static int group;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[][] map = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 땅 분리
        init_land(map);

        // 다리의 경우의 수 저장할 우선순위 큐
        PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        // 경우의 수
        bridge(map, que);

        // 잇기
        bridge_land(que);

        if(rank[find(2)] == group - 2) System.out.println(total);
        else System.out.println(-1);
    }

    private static void bridge_land(PriorityQueue<int[]> que) {

        while(!que.isEmpty()) {
            int[] cur = que.poll();

            int n = union(cur[0], cur[1]);
            if(n == 0) continue;
            total += cur[2];
            if(n == 2) return;

        }
    }

    private static int union(int p, int q) {

        int pp = find(p);
        int pq = find(q);

        if(pp == pq) return 0;

        if(rank[pp] >= rank[pq]) {
            parent[pq] = pp;
            rank[pp] += rank[pq];
            if(rank[pp] == group - 2) return 2;
        } else {
            parent[pp] = pq;
            rank[pq] += rank[pp];
            if(rank[pq] == group - 2) return 2;
        }

        return 1;

    }

    private static int find(int p) {
        if(p == parent[p]) return p;
        return parent[p] = find(parent[p]);
    }

    private static void bridge(int[][] map, PriorityQueue<int[]> que) {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 0) continue;

                for (int d = 0; d < 4; d++) {
                    int nr = i;
                    int nc = j;
                    int time = 0;
                    while(true) {
                        nr = nr + dr[d];
                        nc = nc + dc[d];

                        if(nr >= N || nc >= M || nr < 0 || nc < 0 || map[i][j] == map[nr][nc]) break;
                        if(map[nr][nc] > 0) {
                            if(time < 2) break; 
                            que.offer(new int[] {map[i][j], map[nr][nc], time});
                            break;
                        }
                        time++;
                    }
                }
            }
        }
    }

    private static void init_land(int[][] map) {

        group = 2;
        Queue<int[]> que = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] != 1) continue;
                que.offer(new int[] {i, j});
                map[i][j] = group;
                while(!que.isEmpty()) {
                    int[] cur = que.poll();

                    for (int d = 0; d < 4; d++) {
                        int nr = cur[0] + dr[d];
                        int nc = cur[1] + dc[d];

                        if(nr >= N || nc >= M || nr < 0 || nc < 0 || map[nr][nc] != 1) continue;
                        map[nr][nc] = group;
                        que.offer(new int[] {nr, nc});
                    }
                }
                group++;
            }
        }
        parent = new int[group];
        rank = new int[group];
        for (int i = 0; i < group; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

}