백준 17472번: 다리 만들기 2 (Java)

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

17472번: 다리 만들기 2

 

 

 

 

 

 

 

 

---

 

풀이

섬이 떨어져있고, 이를 최소 길이의 다리를 연결하여 하나로 만든다... -> MST가 떠오릅니다. MST를 찾는 알고리즘에는 크루스칼(유니온 파인드로 V-1개 연결), 프림(우선순위 큐 이용) 알고리즘이 있는데, 본 풀이에서는 크루스칼을 활용합니다.

1. 섬의 개수를 세준 후, 각각의 섬을 1, 2, 3, ... 으로 칠해줍니다. 저는 BFS로 했습니다.

2. 가능한 모든 다리를 만들어서 다리를 저장하는 배열에 담아둡니다. 저는 Bridge라는 class에 from(시작 위치), to(끝 위치), dist(거리)를 저장해두었습니다.

3. 다리 배열을 거리 내림차순으로 배열한 후, 크루스칼로 (섬의 개수)-1개의 다리를 만들어줍시다.

 

다리의 조건이 살짝 장황하게 서술되어있는데, (길이 > 1 조건을 제외하고) 보면 다 MST 편하게 구현하라고 제약조건을 억지로 만든 수준입니다.

골드 상위권의 삼성 기출 문제를 보면, 구현 + 알고리즘이 섞인 문제가 좀 있습니다. 개인적으로는 그렇게 어렵게 느껴지진 않네요. 오히려 큐빙, 모노미노도미노 같은 쌩구현이 시간도 오래 걸리고, 어렵게 느껴집니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static List<Bridge> bridges;
    static int[] p;
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int M, N, islandNum = 0, ans = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 섬의 개수를 세며, 각 섬의 칸을 1~islandNum으로 마킹하여 구분한다.
        visited = new boolean[M][N];
        islandNum = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j] || map[i][j] == 0) continue;
                islandNum++;
                map[i][j] = islandNum;
                visited[i][j] = true;
                bfs(i, j, islandNum);
            }
        }
        
        // 가능한 다리 모두 만들기
        bridges = new ArrayList<>();
        findBridges();
        Collections.sort(bridges);    
        
        makeSet(islandNum+1);
        // 모든 섬이 연결되면 다리의 최소 길이, 아니면 -1 출력
        System.out.println(kruskal(bridges)? ans: -1);
    }
    
    static void bfs(int i, int j, int num) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {i, j});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir], nc = c + dc[dir];
                if (!isIn(nr, nc)) continue;
                if (visited[nr][nc] || map[nr][nc] == 0) continue;
                map[nr][nc] = num;
                visited[nr][nc] = true;
                queue.offer(new int[] {nr, nc});
            }
        }
    }
    
    // 가능한 모든 다리를 찾는 method
    // M, N이 작아서 효율성은 살짝 무시해도 됨
    static void findBridges() {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 0) {
                    for (int k = 0; k < 4; k++) {
                        int r = i + dr[k], c = j + dc[k];
                        int length = 0;
                        while (isIn(r, c)) {
                            if (map[r][c] == map[i][j]) break;
                            else if (map[r][c] > 0) {
                                if (length > 1) {
                                    bridges.add(new Bridge(map[i][j], map[r][c], length));
                                }
                                break;
                            }
                            length++;
                            r += dr[k];
                            c += dc[k];
                        }
                    }
                }
            }
        }
    }
    
    // 크루스칼을 수행하여, 모든 섬이 연결되면 true, 아니면 false 리턴
    static boolean kruskal(List<Bridge> bridges) {
        int cnt = 0;
        for (Bridge b: bridges) {
            if (!union(b.from, b.to)) continue;
            cnt++;
            ans += b.dist;
            if (cnt == islandNum-1) return true;
        }
        return false;
    }
    
    // Bridge class
    static class Bridge implements Comparable<Bridge> {
        int from;
        int to;
        int dist;
        
        public Bridge(int from, int to, int dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(Bridge o) {
            return this.dist - o.dist;
        }
 
        @Override
        public String toString() {
            return "Bridge [from=" + from + ", to=" + to + ", dist=" + dist + "]";
        }
    }
    
    static boolean isIn(int r, int c) {
        return !(r < 0 || r >= M || c < 0 || c >= N);
    }
    
    // Union-Find 관련 methods
    static void makeSet(int N) {
        p = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            p[i] = i;
        }
    }
    static int findRoot(int a) {
        if (a == p[a])
            return a;
        return p[a] = findRoot(p[a]);
    }
    static boolean union(int a, int b) {
        a = findRoot(a);
        b = findRoot(b);
        if (a == b)
            return false;
        p[b] = a;
        return true;
    }
}