[ BOJ ][JAVA][17472] 다리 만들기 2

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	11769	3963	2258	29.405%

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리의 총 길이: 13D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다.총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2)다리 B: 3과 4를 연결 (길이 3)다리 C: 2와 5를 연결 (길이 5)다리 D: 1과 2를 연결 (길이 2)총 길이: 12

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

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

출력

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

제한

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

예제 입력 1

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

예제 출력 1

9

예제 입력 2

7 8
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

예제 출력 2

10

예제 입력 3

7 8
1 0 0 1 1 1 0 0
0 0 1 0 0 0 1 1
0 0 1 0 0 0 1 1
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0

예제 출력 3

9

예제 입력 4

7 7
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1

예제 출력 4

-1

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int n,m;
    static int[][] map;
    static boolean[][] visited;
    static int island = 0;
    static PriorityQueue<edge> pq = new PriorityQueue<edge>();
    static int result = 0;    
    static int[] parents;
    static int bridge_count = 0;

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

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        map = new int[n][m];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++) {
            str = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(str[j]);
            }
        }

        //bfs를 통해 섬에 번호를 부여한다.
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(map[i][j] == 1 && !visited[i][j]) {
                    island++;
                    bfs(new dot(i,j));
                }
            }
        }

        //각 좌표에서 만들 수 있는 최대의 다리를 만든다.
        //다리의 길이는 2이상이어야 하므로, 2 이상이면 pq에 넣어준다.
        visited = new boolean[n][m];
        //show();
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(map[i][j] != 0) {
                    makeBridge(new dot(i,j), map[i][j]);
                }
            }
        }

        //다리를 다 만들었으면 크루스칼 알고리즘을 실행한다.
        //pq의 간선만큼 반복하면서 사이클을 확인하며 최소 간선의 합을 구한다.
        parents = new int[island+1];

        for(int i=0; i<parents.length; i++) {
            parents[i] = i;
        }

        int size = pq.size();
        for(int i=0; i<size; i++) {
            edge tmp = pq.poll();

            int a = find(tmp.s);
            int b = find(tmp.e);

            if(a==b) continue;

            union(tmp.s, tmp.e);
            result += tmp.v;
            bridge_count++;
        }
        //result == 0 이거나 다리의 개수가 섬의 개수 - 1이 아니면 -1을 출력한다.
        if(result == 0 || bridge_count != island-1) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }

    static void bfs(dot d) {
        Queue<dot> q = new LinkedList<dot>();
        visited[d.x][d.y] = true;
        map[d.x][d.y] = island;
        q.add(d);

        while(!q.isEmpty()) {
            dot t = q.poll();
            int x = t.x;
            int y = t.y;

            for(int i=0; i<4; i++) {
                int x2 = x + dx[i];
                int y2 = y + dy[i];

                if(x2>=0 && x2<n && y2>=0 && y2<m && map[x2][y2] == 1 && !visited[x2][y2]) {
                    q.add(new dot(x2,y2));
                    map[x2][y2] = island;
                    visited[x2][y2] = true;
                }
            }

        }
    }
    //상하좌우 중 한 방향으로 계속 이동하면서 다른 섬이 나올 때까지 반복한다.
    //중간에 좌표를 넘어가거나, 자신과 같은 번호가 나오면 좌표와 length를 초기화 한후 넘어간다.
    public static void makeBridge(dot d, int num) {
        int x2 = d.x;
        int y2 = d.y;
        int length = 0;

        for(int i=0; i<4; i++) {
            while(true) {
                x2 = x2 + dx[i];
                y2 = y2 + dy[i];

                if(x2>=0 && x2<n && y2>=0 && y2<m) {
                    if(map[x2][y2] == num) {
                        length = 0;
                        x2 = d.x;
                        y2 = d.y;
                        break;
                    } else if(map[x2][y2] == 0){
                        length++;
                    } else {
                        //1보다 크면 pq에 추가해준다.
                        if(length > 1) {
                            pq.add(new edge(num, map[x2][y2], length));
                        }
                        length = 0;
                        x2 = d.x;
                        y2 = d.y;
                        break;
                    }
                } else {
                    length = 0;
                    x2 = d.x;
                    y2 = d.y;
                    break;
                }
            }
        }
    }
    //크루스칼 알고리즘을 위한 find, union 함수. 
    //외우는게 편하다
    public static int find(int a) {
        if(a == parents[a]) return a;
        parents[a] = find(parents[a]);
        return parents[a];
    }

    public static void union(int s,int e) {
        int aRoot = find(s);
        int bRoot = find(e);

        if(aRoot != bRoot) {
            parents[aRoot] = e;
        } else {
            return;
        }
    }
}

class dot {
    int x;
    int y;

    public dot(int x,int y) {
        this.x = x;
        this.y = y ;
    }
}
// 간선 class : value를 기준으로 compareTo를 overriding하였다.
class edge implements Comparable<edge> {
    int s;
    int e;
    int v;

    public edge(int s,int e,int v) {
        super();
        this.s = s;
        this.e = e;
        this.v = v;
    }

    @Override
    public int compareTo(edge arg0) {
        return arg0.v >= this.v ? -1:1;
    }
}