백준 - 다리만들기2(JAVA)

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

17472번: 다리 만들기 2

 

문제설명

 

1. BFS, DFS, Prim, Kruskal 등 다양한 알고리즘이 사용된다.

 

2. 문제를 잘 분석하고 하나하나 디버깅하며 해결한다.

 

알고리즘

 

1. BFS와 DFS를 사용하여 labeling 후 labeling 한 구역을 하나의 정점이라 생각한다.

 

2. 정점 사이의 거리를 PQ에 넣어준다.

 

3. PQ와 Union-Find를 이용하여 Kruskal 알고리즘을 구현한다.

-> 최단경로를 구하기 위한 방법

 

주의사항

 

1. 단계가 많기 때문에 단계마다 디버깅하며 잘 구현됐는지 확인한다.

 

구현

 

class edge implements Comparable<edge>{
    int start;
    int end;
    int weight;

    public edge(int start, int end, int weight) {
        super();
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(edge o) {
        return this.weight-o.weight;
    }

}
public class Main_다리만들기2 {
    static int map[][];
    static int N;
    static int check[][];
    static int M;
    static int color;
    static int parents[];
    static int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}};
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer s = new StringTokenizer(in.readLine()," ");
        N = Integer.parseInt(s.nextToken());
        M = Integer.parseInt(s.nextToken());
        map = new int[N][M];
        check = new int[N][M];
        LinkedList<int []> queue = new LinkedList<int[]>();
        for (int i = 0; i < N; i++) {
            s = new StringTokenizer(in.readLine()," ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(s.nextToken());
            }
        }
        color =0;
        //////////////////////레이블링과정/////////////////////
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(check[i][j] == 0 && map[i][j] == 1)
                {
                    color++;
                    check[i][j] = color;
                    queue.offer(new int[] {i,j});
                    while(!queue.isEmpty())
                    {
                        int temp[] = queue.poll();
                        int y = temp[0];
                        int x = temp[1];
                        for (int i1 = 0; i1 < 4; i1++) {
                            int ny = dir[i1][0]+y;
                            int nx = dir[i1][1]+x;
                            if(ny > -1 && ny < N && nx < M && nx>-1 && check[ny][nx] == 0 && map[ny][nx] == 1)
                            {
                                check[ny][nx] = color;
                                queue.offer(new int[] {ny,nx});
                            }
                        }
                    }//endwhile
                }//endif
            }
        }
        parents = new int[color+1];
        /////////////////////////////////////////////////////
        int len =0; //다리길이
        PriorityQueue<edge> pq = new PriorityQueue<edge>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(check[i][j] !=0)
                {
                    for (int j2 = 0; j2 < 4; j2++) {
                        int ni = i+dir[j2][0];
                        int nj = j+dir[j2][1];

                        if(ni > -1 && ni < N && nj < M && nj>-1 && check[ni][nj] == 0)
                        {
                            len=0;
                            while(ni > -1 && ni < N && nj < M && nj>-1)
                            {
                                if(check[ni][nj] != 0)
                                {
                                    if(len > 1)
                                    {
                                        pq.offer(new edge(check[i][j], check[ni][nj], len));
                                        break;
                                    }
                                    else
                                        break;
                                }
                                ni = ni+dir[j2][0];
                                nj = nj+dir[j2][1];
                                len++;
                            }
                        }
                    }
                }
            }
        }//endfor

        int result = 0;
        int cnt=0;
        makeset();
        edge ed;
        while(!pq.isEmpty())
        {
            ed = pq.poll();
            if(findset(ed.start) != findset(ed.end)) // 한집합안에없으면
            {
                merge(ed.start,ed.end); //합병
                result+=ed.weight;
                cnt++;
            }
            if(cnt == color-1)
                break;
        }

        System.out.println(cnt==color-1?result:"-1");

    }
    private static void makeset() {
        for (int i = 1; i < color+1; i++) {
            parents[i]=i;
        }
    }
    private static void merge(int x, int y) {
        int v = findset(x);
        int u = findset(y);

        if(v!=u)
            parents[v] = u;
    }
    private static int findset(int x) {
        if(x == parents[x])
            return x;
        return parents[x] = findset(parents[x]);
    }
}