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

17472번: 다리 만들기 2

* 문제 부분이 너무 길어 생략

# 예제 입력

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

# 예제 출력

9

---

[Labeling + BFS + Kruskal (+ Union-Find)]

 이전에 각 원소가 0과 1 중 한 값을 갖는 N x M 행렬이 주어지는 BFS/DFS 문제에서 자주 사용하였던 라벨링(Labeling)을 이용해 각 섬에 번호를 붙였다. 이 과정은 각 섬을 하나의 정점으로 보기위해 필요한 과정인 것 같다.

 

 각 섬에 번호를 붙였으면, 전수조사(Brute-Force)해서 섬에서 다른 섬까지 일직선으로 갈 수 있는(단 거리는 2이상) 모든 경우의 수를 찾아 간선(Edge)의 데이터로 만든 후 List에 넣었다.

 

 간선의 가중치(Weight)를 기준으로 오름차순(ASC)정렬하여 Kruskal 알고리즘을 사용하여 해결하였다.

 

 걱정되었던 것은, 라벨링과 전수조사 방법에서 비슷한 코드가 많이 사용되었고, 중첩loop을 많이 돌아 시간 혹은 메모리 초과 가능성도 존재한다는 것 이었다. 다행히 문제의 입력 수는 그리 크지 않았다. 최대 10 x 10행렬이고, 섬의 개수는 2개이상 6개 이하였기 때문에 괜한 걱정이었다.

 

# Code </>

public class Main {

    static class Edge implements Comparable<Edge>{
        int og, tg, w;
        public Edge(int o, int t, int wt){
            og = o;
            tg = t;
            w = wt;
        }
        @Override
        public int compareTo(Edge o) {
            return w - o.w;
        }
    }
    static class Point{
        int y, x;
        public Point(int y, int x){
            this.y=y;
            this.x=x;
        }
    }
    static int m, n;
    static int map[][];
    static int[] parent;
    
    static Queue<Point> Q = new LinkedList<>();
    static List<Edge> list = new ArrayList<>();
    
    static int[] Y = {-1, 1, 0, 0};
    static int[] X = {0, 0, -1, 1};
    static int cnt = 1;

    static void BFS_Labeling(){

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++){

                if(map[i][j] == 1){
                    cnt++;
                    map[i][j] = cnt;
                    Q.add(new Point(i, j));
                }

                while(!Q.isEmpty()){
                    Point p = Q.poll();
                    int y = p.y;
                    int x = p.x;

                    for(int a=0; a<4; a++){
                        int ny = y+Y[a];
                        int nx = x+X[a];

                        if((ny > 0 && ny <= n) && (nx > 0 && nx <= m) && map[ny][nx] == 1){
                            map[ny][nx] = cnt;
                            Q.add(new Point(ny, nx));
                        }
                    }
                }
            }
        Q.clear();
    }

    //섬에서 다른 섬으로 다리를 놓을 수 있는 경우 list에 추가
    static void BFS(){
        for(int i=1; i<=n; i++) {
            for (int j = 1; j <= m; j++) {

                if(map[i][j] != 0)
                    Q.add(new Point(i, j));

                while(!Q.isEmpty()){
                    Point p = Q.poll();
                    int y = p.y;
                    int x = p.x;

                    for(int a=0; a<4; a++){
                        int ny = y+Y[a];
                        int nx = x+X[a];

                        if((ny > 0 && ny <= n) && (nx > 0 && nx <= m) && map[ny][nx] == 0){
                            int weight = 1;

                            while((ny+Y[a] > 0 && ny+Y[a] <= n) && (nx+X[a] > 0 && nx+X[a] <= m)){

                                ny += Y[a];
                                nx += X[a];
                                if(map[ny][nx] != 0) {
                                    if(weight > 1) {
                                        //System.out.println((map[y][x]) + "에서 " + (map[ny][nx]) + "로 다리 길이는 " + weight + " // y:" + y + " x:" + x + " ny:" + ny + " nx:" + nx);
                                        list.add(new Edge(map[y][x] - 1, map[ny][nx] - 1, weight));
                                    }
                                    break;
                                }
                                weight++;
                            }
                        }
                    }
                }
            }
        }
    }
    /* Union-Find */
    static int getParent(int x){
        if(parent[x] == x) return x;
        return getParent(parent[x]);
    }
    static void unionParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(a > b) parent[a] = b;
        else parent[b] = a;
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);
        return a == b?true:false;
    }
    /* Union-Find */

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n+1][m+1];

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        BFS_Labeling();
        BFS();

        parent = new int[cnt];
        for(int i=1; i<cnt; i++)
            parent[i] = i;

        Collections.sort(list);

        int sum = 0;
        for(int i=0; i<list.size(); i++){
            Edge edge = list.get(i);

            if(!findParent(edge.og, edge.tg)){
                sum += edge.w;
                unionParent(edge.og, edge.tg);
            }
        }
        boolean flag = true;
        for(int i=1; i<parent.length-1; i++)
            if(!findParent(parent[i], parent[i+1]))
                flag = false;

        System.out.println();*/

        if(flag)
            System.out.println(sum);
        else
            System.out.println(-1);
    }
}