백준 다리 만들기 2

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다.
둘째 줄부터 N개의 줄에 지도의 정보가 주어진다.
각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다.
0은 바다, 1은 땅을 의미한다.

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다.
모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

내가 이 문제를 보고 생각해본 부분

dfs 함수: 각 섬을 탐색하며 섬마다 고유 번호를 할당한다. 
방문하지 않은 땅은 같은 섬으로 묶는다.
edges 리스트: 각 섬에서 상하좌우 방향으로 바다 칸을 건너 뻗어나가면서, 2칸 이상이면서 다른 섬에 닿는 다리 후보를 조사해 저장한다.
MST (최소 스패닝 트리) 알고리즘: 섬들을 최소 비용으로 연결하기 위해 크루스칼 알고리즘을 사용한다.
parent 배열로 유니온 파인드(Disjoint Set Union) 구조를 구현해 섬들이 연결되어 있는지 체크하여 사이클 방지 및 연결 상태를 관리한다.
모든 섬이 연결되면 다리 길이 합산 결과 출력, 불가능하면 -1 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

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

// 백준 17472번 문제
public class Main1342 {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int islandCount = 0;
    static class Edge implements Comparable<Edge> {
        int from, to, cost;
        public Edge(int f, int t, int c) {
            from = f; to = t; cost = c;
        }
        public int compareTo(Edge o) {
            return cost - o.cost;
        }
    }

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    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];
        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());
            }
        }

        // 1. 섬 번호 붙이기
        visited = new boolean[N][M];
        islandCount = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    islandCount++;
                    dfs(i, j, islandCount);
                }
            }
        }

        // 2. 다리 후보 찾기
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] > 0) {
                    for (int d = 0; d < 4; d++) {
                        int length = 0;
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        while (isIn(nx, ny) && map[nx][ny] == 0) {
                            length++;
                            nx += dx[d];
                            ny += dy[d];
                        }
                        if (isIn(nx, ny) && map[nx][ny] != map[i][j] && map[nx][ny] > 0 && length >= 2) {
                            edges.add(new Edge(map[i][j], map[nx][ny], length));
                        }
                    }
                }
            }
        }

        // 3. MST 구성
        parent = new int[islandCount + 1];
        for (int i = 1; i <= islandCount; i++)
            parent[i] = i;
        Collections.sort(edges);

        int count = 0;
        int result = 0;
        for (Edge e : edges) {
            int a = find(e.from);
            int b = find(e.to);
            if (a != b) {
                union(a, b);
                result += e.cost;
                count++;
            }
            if (count == islandCount - 1)
                break;
        }

        if (count == islandCount - 1)
            System.out.println(result);
        else
            System.out.println(-1);
    }

    static void dfs(int x, int y, int id) {
        visited[x][y] = true;
        map[x][y] = id;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (isIn(nx, ny) && !visited[nx][ny] && map[nx][ny] == 1) {
                dfs(nx, ny, id);
            }
        }
    }

    static int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b)
            parent[b] = a;
    }

    static boolean isIn(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.