[BOJ 17472 - 다리 만들기 2] - 최소스패닝트리, 프림알고리즘

BOJ 17472 - 다리만들기 2

내일 현대오토에버 코테를 앞두고 빡센 구현 문제 하나 풀어보았다.

주어진 이차원 평면에서 조건에 맞게 다리를 건설하고, 모든 경로를 잇는 다리 길이의 총합의 최소를 구하는 문제이다.

접근법

각각의 섬을 그래프의 노드로, 다리를 간선으로 생각할 수 있다.

1. 먼저 각각의 섬을 구분짓는다.
2. 조건에 맞는 가능한 모든 다리를 건설한다. 동일한 섬을 연결한다면 최소 길이의 다리만 남긴다.
3. 주어진 정보로 그래프를 구성한다.
4. 최소스패닝트리(MST)를 구한다.

최소 스패닝 트리(MST)

최소 스패닝 트리(Minimum Spanning Tree, MST)는 연결된 무향 그래프에서 모든 정점을 포함하는 부분 그래프 중 간선 가중치의 합이 최소인 트리를 말합니다. 여기서 "스패닝 트리"란, 그래프의 모든 정점을 포함하되 사이클이 없는 연결 그래프입니다. 즉, MST는 그래프 내의 모든 정점을 연결하면서 간선 비용을 최소화하는 구조입니다.

최소 스패닝 트리의 특징은

• 트리 구조이며 따라서 사이클이 없다. 모든 정점이 연결되어있다.
• n개의 노드에 대해 간선의 개수는 n-1이다.
• 간선 가중치의 합이 최소이다.

프림 알고리즘 (Prim’s Algorithm)

프림 알고리즘은 최소신장트리를 구하는 알고리즘이며 직관적이어서 이해가 쉽다.
현재까지 구성한 MST에 인접한 가장 짧은 간선을 지속적으로 선택해 나아가면 된다.

우선순위큐를 통해 쉽게 구현이 가능하며,
시간복잡도는 모든 간선만큼 반복하며 우선순위큐에 삽입, 삭제를 하므로 O(E logV)이다.

프림 알고리즘은 하나의 정점에서 시작하여 인접한 간선 중 가장 낮은 가중치를 가진 간선을 선택해 MST에 추가한다. 이후 추가된 정점의 인접 간선 중 최소 가중치 간선을 선택하는 과정을 반복하여 모든 정점이 포함될 때까지 진행한다.

전체 코드

구현문제를 풀때는 최대한 간단하게 작은 단위의 함수들로 쪼개어 푸는 편이다.

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

public class Main {
    static int[][] map;
    static int row;
    static int col;

    static int[] dRow = {-1, 1, 0, 0};
    static int[] dCol = {0, 0, -1, 1};

    static int[][] adjs;

    static class Bridge {
        int to;
        int length = -1;
    }

    static boolean isValidRange(int r, int c) {
        return 0 <= r && r < row && 0 <= c && c < col;
    }

    static void bfsToNumbering(int r, int c, int islandNum, boolean[][] visited) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{r, c});

        while(!q.isEmpty()) {
            int[] tmp = q.poll();
            int tmpR = tmp[0];
            int tmpC = tmp[1];

            if(visited[tmpR][tmpC]) continue;
            visited[tmpR][tmpC] = true;
            map[tmpR][tmpC] = islandNum;

            for(int i = 0; i < 4; i++) {
                int nextR = tmpR + dRow[i];
                int nextC = tmpC + dCol[i];
                if(islandNum == 2 && i == 1) {
                    int here = 1;
                }
                if(isValidRange(nextR, nextC) && map[nextR][nextC] != 0) {
                    q.add(new int[]{nextR, nextC});
                }
            }
        }
    }

    static void numberingIsland() {
        boolean[][] visited = new boolean[row][col];

        int islandNum = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(map[i][j] == 1 && !visited[i][j]) {
                    bfsToNumbering(i, j, ++islandNum, visited);
                }
            }
        }

        adjs = new int[islandNum + 1][islandNum + 1];
        for(int i = 0; i < islandNum + 1; i++) {
            Arrays.fill(adjs[i], Integer.MAX_VALUE);
            adjs[i][i] = 0;
        }
    }

    static boolean isNearWater(int r, int c) {
        for(int i = 0; i < 4; i++) {
            int nextR = r + dRow[i];
            int nextC = c + dCol[i];
            if(isValidRange(nextR, nextC) && map[nextR][nextC] == 0) return true;
        }
        return false;
    }

    static Bridge makeBridge(int r, int c, int dRow, int dCol, int startIslandNum) {
        Bridge b = new Bridge();
        int len = 0;
        while(isValidRange(r, c) && map[r][c] == 0) {
            r += dRow;
            c += dCol;
            len++;
        }

        if(isValidRange(r, c) && map[r][c] != startIslandNum) {
            b.length = len;
            b.to = map[r][c];
        }

        return b;
    }

    static void setAdj(int r, int c) {
        int tmpIslandNum = map[r][c];

        for(int i = 0; i < 4; i++) {
            int nextR = r + dRow[i];
            int nextC = c + dCol[i];
            if(isValidRange(nextR, nextC) && map[nextR][nextC] == 0) {
                Bridge b = makeBridge(nextR, nextC, dRow[i], dCol[i], tmpIslandNum);
                if(b.length >= 2) {
                    adjs[tmpIslandNum][b.to] = Math.min(adjs[tmpIslandNum][b.to], b.length);
                    adjs[b.to][tmpIslandNum] = Math.min(adjs[b.to][tmpIslandNum], b.length);
                }
            }
        }
    }

    static void setAdjs() {
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(map[i][j] != 0 && isNearWater(i, j)) {
                    setAdj(i, j);
                }
            }
        }
    }

    public static int getMinBridgeSum() {
        boolean[] visited = new boolean[adjs.length];

        int count = 0;
        int sumOfChosenBridge = 0;

        //len, isLandNum
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.add(new int[]{0, 1});

        while (!pq.isEmpty()) {
            int[] tmp = pq.poll();
            int len = tmp[0];
            int tmpNode = tmp[1];

            if(visited[tmpNode]) continue;
            visited[tmpNode] = true;
            count++;
            sumOfChosenBridge += len;

            if(count == adjs.length - 1) break;

            for(int i = 1; i < adjs.length; i++) {
                if(adjs[tmpNode][i] != Integer.MAX_VALUE && !visited[i]) {
                    pq.add(new int[]{adjs[tmpNode][i], i});
                }
            }
        }

        if(count != adjs.length - 1) return -1;

        return sumOfChosenBridge;
    }

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

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());

        map = new int[row][col];

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

        numberingIsland(); //각각의 섬을 구분짓는다.
        setAdjs(); //그래프를 구성한다

        System.out.println(getMinBridgeSum()); //최소신장트리의 간선의 합을 출력한다.
    }
}