[백준 17472] 다리 만들기2 / 자바 / dfs + 크루스칼 알고리즘 **

#문제         

레벨: G1
알고리즘: dfs 
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

 

전체적인 알고리즘 과정은 이렇게 된다.

1. 전체를 탐색하며 섬에게 숫자를 매겨준다.

2. 섬끼리 연결 가능한 다리를 다 찾는다.

3. 그 중 전체를 포함하지만 최소인 다리들을 찾는다.     <---- 주목

 

G1 정도 문제를 푸시는 분들이라면 1,2 번 정도는 머리 속에서 어떻게 구현할지 감이 잡힐 것이다. 그래도 간단하게 설명해보겠다.

 

1. 섬에게 번호를 지목한다. 

이중 for문으로 map 전체를 순회하면서 숫자 1을 찾는다. 숫자 1을 찾으면 4방향으로 dfs 혹은 bfs하여 섬의 번호를 새겨준다. 

검정색: 이중 for문 탐색 방향

파란색: 이중 for문 지나간 흔적

빨간색: 섬의 번호 부여 

'

 

2. 섬끼리 연결 가능한 다리를 다 찾는다.

이중 for문을 돌며 0이 아닌 숫자가 부여된 숫자 찾아 그 인덱스에서 4방향으로 전부 탐색된다. 그리고 섬이랑 마주한 빨간색 선들만 다리배열에 추가해준다. 

 

3. 그 중 전체를 포함하지만 최소인 다리들을 찾는다.

여기서 크루스칼 알고리즘이 사용된다. 

크리스칼 알고리즘이란 최소신장트리를 찾는 알고리즘이다.

그림으로 설명하겠다. 이와 같이 노드랑 연결 선들이 있다. 최소한 선으로 모든 노드를 연결하고 싶다. 아래와 같은 방법으로 찾을 것이다.

1. 오름차순으로 선을 정렬한다. 

2. 정렬된 순서대로 선택하며 선에 포함된 노드들의 부모노드들을 낮은 숫자의 번호로 바꾼다.

3. 부모가 적혀져있는 배열에 자기 번호가 안 써져있다는 건 이미 연결되어있다는 뜻이므로 그 선은 사용하지 않는다.

모든 선 표시

크리스칼 알고리즘 후

 

parent배열
 1 | 2 | 3 | 4 | 5
-------------------
 1 | 2 | 3 | 4 | 5|
 
 line 배열
2-1 (1)   ->  4-5 (1)   -> 1-3(2)  -> 2-3(3)  ->  2-4 (4)  -> 3-4 (5)   ->   3-5 (6)



1.   2-1(1) 선택 후 parnet 배열

 1 | 2 | 3 | 4 | 5
-------------------
 1 | 1 | 3 | 4 | 5|


2.   4-5(1) 선택 후 parnet 배열

 1 | 2 | 3 | 4 | 5
-------------------
 1 | 1 | 3 | 4 | 4|
 
 
3.   1-3(2) 선택 후 parnet 배열

 1 | 2 | 3 | 4 | 5
-------------------
 1 | 1 | 1 | 4 | 4|
 
 
  
4.   2-3(3) 선택 후 parnet 배열    <----위 배열에서 1,3의 parent는 이미 1로 같으니  아무것도 일어나지 않는다.

 1 | 2 | 3 | 4 | 5
-------------------
 1 | 1 | 1 | 4 | 4|
 
 
 5.   2-4(4) 선택 후 parnet 배열   

 1 | 2 | 3 | 4 | 5
-------------------
 1 | 1 | 1 | 1 | 4|
 
 
 6.   3-4(4) 선택 후 parnet 배열    <----위 배열에서 3,4의 parent는 이미 1로 같으니  아무것도 일어나지 않는다.

 1 | 2 | 3 | 4 | 5
-------------------
 1 | 1 | 1 | 1 | 4|
 
 
 7.   3-5(6) 선택 후 parnet 배열    <---- 5의 부모는 4이고 4의 부모는 1이다. 3의 부모도 1이고 1의 부모는 1이다. 
                                           최상위 부모가 1로 같으므로 아무것도 일어나지 않는다.
 1 | 2 | 3 | 4 | 5
-------------------
 1 | 1 | 1 | 1 | 4|

 

 

 

---

#풀이 코드      

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int islandCount = 0;

    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());
            }
        }

        numberingIslands();
        List<Bridge> bridges = findBridges();
        int result = kruskal(bridges);
        System.out.println(result);
    }

    static void numberingIslands() {
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    islandCount++;
                    dfs(i, j, visited);
                }
            }
        }
    }

//섬 숫자로 구별
    static void dfs(int x, int y, boolean[][] visited) {
        visited[x][y] = true;
        map[x][y] = islandCount;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] == 1 && !visited[nx][ny]) {
                dfs(nx, ny, visited);
            }
        }
    }

    static List<Bridge> findBridges() {
        List<Bridge> bridges = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    findBridge(i, j, bridges);
                }
            }
        }
        return bridges;
    }

    static void findBridge(int x, int y, List<Bridge> bridges) {
        int start = map[x][y];
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            int length = 0;
            while (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] != start) {
                if (map[nx][ny] != 0) {
                    if (length > 1) {
                        bridges.add(new Bridge(start, map[nx][ny], length));
                    }
                    break;
                }
                length++;
                nx += dx[dir];
                ny += dy[dir];
            }
        }
    }

//최소 신장 트리 찾기
    static int kruskal(List<Bridge> bridges) {
        bridges.sort(Comparator.comparingInt(b -> b.length));
        int[] parent = new int[islandCount + 1];
        for (int i = 1; i <= islandCount; i++) parent[i] = i;

        int totalLength = 0;
        int connectedCount = 0;

        for (Bridge bridge : bridges) {
            if (find(parent, bridge.start) != find(parent, bridge.end)) { //최상위 부모가 같은지 확인.
                union(parent, bridge.start, bridge.end); // 같지 않다면 부모 변경
                totalLength += bridge.length;
                connectedCount++;
            }
        }

        return connectedCount == islandCount - 1 ? totalLength : -1;
    }

    static int find(int[] parent, int x) {
        if (parent[x] != x) { //부모가 자기 자신이 아니라면 연결되어있다는 것이므로 재귀로 최상위 부모 찾음
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

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

    static class Bridge {
        int start, end, length;

        Bridge(int start, int end, int length) {
            this.start = start;
            this.end = end;
            this.length = length;
        }
    }
}