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

백준 17472번 '다리 만들기 2' 풀이입니다. 섬을 정점으로, 섬 사이 최소 다리 길이를 간선으로 구성한 뒤 최소 신장 트리(MST)를 구하는 문제입니다. BFS로 섬 라벨링, 직선 탐색으로 다리 후보 구성, 크루스칼 알고리즘으로 최소 연결 비용을 계산했습니다. 섬 사이 최소 다리까지는 구했지만 MST 개념을 몰라서 크루스칼을 찾아 적용했습니다.

---

📌 문제 정보

• 번호: 17472
• 제목: 다리 만들기 2
• 난이도: Gold 3
• 분류: 그래프, 최소 신장 트리(MST), 분리 집합(Union-Find), BFS

---

💡 접근 방식

섬을 정점으로 보고, 섬 사이를 연결할 수 있는 최소 다리 길이를 간선으로 구성한 뒤 최소 신장 트리를 구하는 방식으로 해결했습니다.

1단계 - 섬 라벨링

BFS를 사용해 연결된 땅을 하나의 섬으로 묶고 번호를 부여했습니다.

2단계 - 다리 후보 탐색

각 섬에서 최소 길이의 다리를 구했습니다. dist[i][j]에 섬 i와 j 사이의 최소 다리 길이를 저장했습니다.

3단계 - MST 구성

dist 배열을 기반으로 간선 리스트를 생성하고, 크루스칼 알고리즘을 이용해 최소 연결 비용을 계산했습니다.

---

💻 핵심 코드

static int kruskal(int landNum) {
    List<Edge> edges = new ArrayList<>();
    for (int i = 1; i <= landNum; i++) {
        for (int j = i + 1; j <= landNum; j++) {
            if (dist[i][j] != Integer.MAX_VALUE) {
                edges.add(new Edge(i, j, dist[i][j]));
            }
        }
    }
    Collections.sort(edges);
    parent = new int[landNum + 1];
    for (int i = 1; i <= landNum; i++) parent[i] = i;

    int total = 0, used = 0;
    for (Edge e : edges) {
        if (union(e.from, e.to)) {
            total += e.weight;
            used++;
        }
    }
    return (used == landNum - 1) ? total : -1;
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(NM + E log E)
• 공간 복잡도: O(NM + E)

---

📄 전체 코드

package B17472;

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static final int[] dr = {-1, 1, 0, 0};
    static final int[] dc = {0, 0, -1, 1};
    static int[][] dist;

    static class Edge implements Comparable<Edge> {
        int from, to, length;
        Edge(int from, int to, int length) {
            this.from = from; this.to = to; this.length = length;
        }
        @Override public int compareTo(Edge o) { return this.length - o.length; }
    }

    static int[] parent;

    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());
        map = new int[N][M];
        visited = new boolean[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());
        }
        int landNum = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (map[i][j] == 1 && !visited[i][j]) checkLand(i, j, ++landNum);
        buildBridge(landNum);
        System.out.println(kruskal(landNum));
    }

    static void checkLand(int row, int col, int landNum) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{row, col});
        visited[row][col] = true;
        map[row][col] = landNum;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int k = 0; k < 4; k++) {
                int nr = cur[0] + dr[k], nc = cur[1] + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc] || map[nr][nc] != 1) continue;
                visited[nr][nc] = true; map[nr][nc] = landNum; queue.add(new int[]{nr, nc});
            }
        }
    }

    static void buildBridge(int landNum) {
        dist = new int[landNum + 1][landNum + 1];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) continue;
                int from = map[i][j];
                for (int k = 0; k < 4; k++) {
                    int nr = i + dr[k], nc = j + dc[k], len = 0;
                    while (nr >= 0 && nr < N && nc >= 0 && nc < M) {
                        if (map[nr][nc] == from) break;
                        else if (map[nr][nc] == 0) { len++; nr += dr[k]; nc += dc[k]; }
                        else {
                            int to = map[nr][nc];
                            if (len >= 2) { int min = Math.min(dist[from][to], len); dist[from][to] = min; dist[to][from] = min; }
                            break;
                        }
                    }
                }
            }
        }
    }

    static int kruskal(int landNum) {
        List<Edge> edges = new ArrayList<>();
        for (int i = 1; i <= landNum; i++)
            for (int j = i + 1; j <= landNum; j++)
                if (dist[i][j] != Integer.MAX_VALUE) edges.add(new Edge(i, j, dist[i][j]));
        Collections.sort(edges);
        parent = new int[landNum + 1];
        for (int i = 1; i <= landNum; i++) parent[i] = i;
        int sum = 0, cnt = 0;
        for (Edge e : edges) if (union(e.from, e.to)) { sum += e.length; cnt++; }
        return cnt == landNum - 1 ? sum : -1;
    }

    static int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
    static boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; parent[b] = a; return true; }
}