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

다리 만들기2

풀이

섬으로 이루어진 나라가 있고, 이 섬들을 다리로 연결하려고 한다.

그렇기 때문에 먼저 섬들을 구분해야한다. 섬을 구분하기 위해 bfs를 이용해서 섬인 곳을 분리하여 따로 배열에 저장한다.

그 다음 섬들끼리 다리를 이어 길이가 2이상인 다리들을 만들고 최소 신장트리를 만들었을 때 다리의 길이의 합이 최소가 되는 값을 구하면 된다.

섬들끼리 연결할 때 최소 신장트리가 만들어지지 않았다면 -1을 출력하고 모든 섬 간의 다리 길이가 1인 경우 우선 순위 큐가 비어있기때문에 -1을 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int n, m;
    static boolean[][] visit;
    static int[][] map;
    static ArrayList<Island> islands;
    static int[] p;
    static PriorityQueue<Bridge> priorityQueue;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] num = br.readLine().split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);
        map = new int[n][m];
        visit = new boolean[n][m];
        islands = new ArrayList<>();

        String[] line;
        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(line[j]);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1 && !visit[i][j]) {
                    bfs(i, j);
                }
            }
        }

        int len = islands.size();
        //        int[][] graph = new int[len][len];
        p = new int[len];

        for (int i = 0; i < len; i++)
            p[i] = i;

        priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i != j) {
                    calcDist(i, j);
                }
            }
        }

        int sum = 0;
        if (priorityQueue.isEmpty()) {
            bw.write("-1\n");
        } else {
            while (!priorityQueue.isEmpty()) {
                Bridge bridge = priorityQueue.poll();
                int a = bridge.x;
                int b = bridge.y;

                if (union(a, b)) {
                    sum += bridge.w;
                }
            }
            for (int i = 0; i < len; i++)
                find(i);
            if (Arrays.stream(p).allMatch(x -> x == p[0]))
                bw.write(sum + "\n");
            else
                bw.write("-1\n");
        }
        br.close();
        bw.close();
    }

    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if (aRoot != bRoot) {
            p[bRoot] = aRoot;
            return true;
        } else
            return false;
    }

    private static int find(int a) {
        if (a == p[a])
            return a;
        else {
            int y = find(p[a]);
            p[a] = y;
            return y;
        }
    }

    private static void calcDist(int i, int j) {
        int max = Integer.MAX_VALUE;
        Island a = islands.get(i);
        Island b = islands.get(j);
        for (Pos p1 : a.part) {
            for (Pos p2 : b.part) {
                if (p1.x == p2.x) {
                    if (checkLand(p1.y, p2.y, 0, p1.x)) {
                        int d = Math.abs(p1.y - p2.y) - 1;
                        if (d != 1)
                            max = Math.min(max, d);
                    }
                } else if (p1.y == p2.y) {
                    if (checkLand(p1.x, p2.x, 1, p1.y)) {
                        int d = Math.abs(p1.x - p2.x) - 1;
                        if (d != 1)
                            max = Math.min(max, d);
                    }
                }
            }
        }
        if (max != Integer.MAX_VALUE)
            priorityQueue.offer(new Bridge(i, j, max));
    }

    private static boolean checkLand(int a, int b, int dir, int s) {
        // row
        int start = a;
        int dest = b;
        if (a > b) {
            start = b;
            dest = a;
        }
        if (dir == 0) {
            for (int i = start + 1; i < dest; i++) {
                if (map[s][i] == 1)
                    return false;
            }
        } else {
            for (int i = start + 1; i < dest; i++) {
                if (map[i][s] == 1)
                    return false;
            }
        }
        return true;
    }

    private static void bfs(int x, int y) {
        Island island = new Island();
        Queue<Pos> queue = new LinkedList<>();
        queue.offer(new Pos(x, y));

        while (!queue.isEmpty()) {
            Pos p = queue.poll();
            island.part.add(p);
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if ((nx >= 0 && nx < n) && (ny >= 0 && ny < m)) {
                    if (!visit[nx][ny] && map[nx][ny] == 1) {
                        visit[nx][ny] = true;
                        queue.offer(new Pos(nx, ny));
                    }
                }
            }
        }
        islands.add(island);
    }
}

class Island {
    ArrayList<Pos> part;

    public Island() {
        part = new ArrayList<>();
    }

    @Override
    public String toString() {
        return "Island{" +
                "part=" + part +
                '}';
    }
}

class Pos {
    int x;
    int y;

    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Pos{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

class Bridge implements Comparable<Bridge> {
    int x;
    int y;
    int w;

    public Bridge(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }

    @Override
    public String toString() {
        return "Bridge{" +
                "x=" + x +
                ", y=" + y +
                ", w=" + w +
                '}';
    }

    @Override
    public int compareTo(Bridge o) {
        return Integer.compare(this.w, o.w);
    }
}