[백준] 17472: 다리 만들기 2 JAVA

접근

여러 알고리즘이 합쳐져 있어서 구현 난이도가 꽤 빡센 문제였다. (170줄...) 크게 나눠보면

1. bfs로 서로 땅이 연결된 섬들을 구함

2. 각 섬들 간에 연결 가능한 다리를 찾음

3. 크루스칼로 다리 길이의 최소 합을 구함

의 과정으로 진행된다. 이제 하나씩 자세히 들여다보자.

 

먼저 1번에서는, 지도가 최대 10x10으로 작으므로 한 칸씩 이동하며 1을 발견한다면 연결된 땅들을 하나의 섬으로 표시해준다. 0은 바다, 1은 땅이므로 섬의 번호는 2번부터 시작하도록 했다. 나중에 크루스칼 알고리즘을 돌리며 모든 섬이 연결되었는지를 확인하기 위해서는 섬의 개수가 필요하기 때문에, 섬의 번호를 표시함과 동시에 총 섬의 개수를 리턴해준다. 이 때, 섬의 번호는 2부터 시작했기 때문에 2를 뺀 값을 리턴했다.

 

2번에서도 마찬가지로, 지도가 작기 때문에 한 칸씩 이동하며 섬이 나온다면 근처 섬을 찾도록 한다. 다만 상하좌우 4방향을 모두 볼 필요는 없다. A섬에서 아래로 내려가 B섬과 만나는 다리를 찾았는데, B섬에서 위로 올라가 A섬과 만나는 다리를 또 찾게된다면 동일한 다리를 두번 탐색하게 되기 때문이다. 

0이면 바다이므로 다리의 길이를 +1해주고, 시작 지점의 번호와 같다면 내륙을 통한 것이기 때문에 넘어간다. 아예 다른 번호가 나온다면 근처 섬을 찾은 것이다. 그렇게 Edge를 만들어 우선순위 큐에 넣어준다. 다리를 찾았더라도 그 길이가 1이라면 넘어가야 한다.

 

이제 복잡한 전처리는 모두 끝났으니, 3번에서는 익숙한 크루스칼 알고리즘을 돌려주면 된다. 그런데 모든 섬이 연결되지 않는 경우가 존재할 수 있으므로, 연결된 다리의 수와 섬의 수를 비교해야 한다. bridgeCnt = islandCnt -1이라면 모든 섬이 연결된 것이고, 아니라면 -1을 출력해야 한다. 

 

코드

package week7;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ17472 {
    static class Pos{
        int x, y;

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

    static class Edge implements Comparable<Edge>{
        int from, to, dist;

        public Edge(int from, int to, int dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return this.dist - o.dist;
        }
    }

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

    static int[][] islandMap;
    static int[] root;
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 변수 초기화
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        islandMap = new int[n][m];

        // 지도 정보 저장
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++)
                islandMap[i][j] = Integer.parseInt(st.nextToken());
        }
        
        // 섬 찾기
        int islandCnt = findIsland();

        // 섬들 간의 거리 계산
        PriorityQueue<Edge> pq = findBridge();

        // 크루스칼 알고리즘
        System.out.println(kruskal(pq, islandCnt));
    }

    private static int kruskal(PriorityQueue<Edge> pq, int islandCnt) {
        int bridgeCnt = 0;
        int bridgeLen = 0;

        root = new int[islandCnt+2];
        for (int i = 0; i < islandCnt+2; i++)
            root[i] = i;

        while(!pq.isEmpty()){
            if(bridgeCnt == islandCnt - 1) break;

            Edge e = pq.poll();

            int r1 = findRoot(e.from);
            int r2 = findRoot(e.to);

            if(r1 == r2) continue;

            union(r1, r2);
            bridgeCnt++;
            bridgeLen += e.dist;
        }

        return bridgeCnt == islandCnt-1 ? bridgeLen : -1;
    }

    private static PriorityQueue<Edge> findBridge() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(islandMap[i][j] == 0) continue;

                for (int d = 0; d < 2; d++) { // 다리가 중복될 수 있으므로 4방향을 다 볼 필요가 없음
                    int x = i, y = j;
                    int dist = 0;

                    // d 방향으로 쭉 이동하다가 다른 섬을 만나면 다리 연결
                    while(true){
                        x += dx[d];
                        y += dy[d];
                        // 범위를 벗어나거나 같은 섬이라면 그만 본다
                        if(!inBound(x, y) || islandMap[x][y] == islandMap[i][j]) break;

                        if(islandMap[x][y] == 0) dist++;
                        else if(islandMap[x][y] != islandMap[i][j]){
                            // 다른 섬을 찾으면 길이가 2 이상인 다리만 연결
                            if(dist > 1) pq.add(new Edge(islandMap[i][j], islandMap[x][y], dist));
                            break;
                        }
                    }
                }
            }
        }

        return pq;
    }

    private static int findIsland() {
        int islandNum = 2;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(islandMap[i][j] != 1) continue;

                checkIsland(i, j, islandNum++);
            }
        }
        return islandNum - 2;
    }

    private static void checkIsland(int x, int y, int islandNum) {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(x, y));

        while(!q.isEmpty()){
            Pos p = q.poll();
            if(islandMap[p.x][p.y] == islandNum) continue;
            islandMap[p.x][p.y] = islandNum;

            for (int d = 0; d < 4; d++) {
                int nx = p.x + dx[d];
                int ny = p.y + dy[d];

                if(!inBound(nx, ny) || islandMap[nx][ny] == 0) continue;
                q.add(new Pos(nx, ny));
            }
        }
    }

    static boolean inBound(int x, int y){
        return !(x < 0 || y < 0 || x >= n || y >= m);
    }

    static int findRoot(int n){
        if(root[n] == n) return n;
        return root[n] = findRoot(root[n]);
    }

    static void union(int r1, int r2){
        root[r1] = r2;
    }
}