(백준) 다리만들기2 - 17472 [java]

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

 

🐢 설명

2차원 맵에 있는 섬들을 직선의 다리를 놓아서 연결하되 다리의 총 길이가 최소가 되도록 하는 문제이다.

 

1. 모든 섬들을 구분해서 번호를 맺기 위해 DFS를 사용했다.
2. 만들수 있는 모든 다리를 만들고 다리를 비용이 낮은 순으로 탐색하기 위해 우선순위큐를 사용했다.
3. 각 모든 섬들을 다리로 묶어서 연결됨을 나타내기위해 union-find를 사용했다
   • 우선순위 큐에 담긴 모든 다리를 하나씩 확인하면서 해당 다리가 잇는 섬이 이미 연결되었는지 안되었는지를 확인하고, 연결이 안되었다면 연결시키고 다리비용을 추가시켰다.
4. 마지막으로 모든 다리에 대해 비교를 끝내고 모든 섬들의 부모를 확인해서 하나라도 다른 섬이 있다면 연결되지 않았다고 판단했다.

 

🐢코드

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

public class Main {
    static int N, M;
    static int[][] board;
    static boolean[][] visited;
    static int[] parents;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static PriorityQueue<Bridge> pq = new PriorityQueue<>(Comparator.comparingInt(b -> b.len));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        board = new int[N][M];

        for (int i = 0; i < N; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(input[j]);
            }
        }

        findAllIsland();
        makeAllBridge();
        int answer = matchingBrdige();

        int other = find(parents[1]);
        for (int i = 2; i < parents.length; i++) {
            if (other != find(parents[i])) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(answer);
    }

    private static int matchingBrdige() {
        int totalBridgeLen = 0;
        while (!pq.isEmpty()) {
            Bridge bridge = pq.poll();

            int landA = find(bridge.landA);
            int landB = find(bridge.landB);

            if (landA != landB) {
                union(landA, landB);
                totalBridgeLen += bridge.len;
            }
        }
        return totalBridgeLen;
    }

    private static void union(int landA, int landB) {
        parents[landA] = landB;
    }

    private static int find(int land) {
        if (parents[land] == land) return land;
        return parents[land] = find(parents[land]);
    }

    private static void makeAllBridge() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] > 0) {
                    setBridge(i, j);
                }
            }
        }
    }

    private static void setBridge(int y, int x) {
        int nowLand = board[y][x];

        for (int d = 0; d < 4; d++) {
            boolean flag = false;
            int ny = y, nx = x;
            int len = 0;

            while (true) {
                ny += dy[d];
                nx += dx[d];

                if (ny < 0 || nx < 0 || ny >= N || nx >= M) break;
                if (board[ny][nx] == nowLand) break;
                if (board[ny][nx] > 0 && len < 2) break;
                if (board[ny][nx] > 0 && len >= 2) {
                    flag = true;
                    break;
                }
                len++;
            }
            if (flag) pq.add(new Bridge(nowLand, board[ny][nx], len));
        }
    }

    private static void findAllIsland() {
        visited = new boolean[N][M];
        int indexing = 1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && board[i][j] != 0) {
                    DFS(i, j, indexing++);
                }
            }
        }

        parents = new int[indexing];
        for (int i = 1; i < indexing; i++)
            parents[i] = i;
    }

    private static void DFS(int y, int x, int indexing) {
        if (y < 0 || x < 0 || y >= N || x >= M || board[y][x] == 0 || visited[y][x])
            return;

        board[y][x] = indexing;
        visited[y][x] = true;

        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];
            DFS(ny, nx, indexing);
        }
    }

    private static class Bridge {
        int landA;
        int landB;
        int len;

        public Bridge(int landA, int landB, int len) {
            this.landA = landA;
            this.landB = landB;
            this.len = len;
        }
    }
}

🐢 마무리