[BOJ] 17472. 다리 만들기2

이 문제는 여지껏 배운 다양한 알고리즘을 거의다 사용해야 풀 수 있다.

다음과 같은 로직으로 구현하였다.
1. BFS 또는 DFS 를 이용하여 섬을 찾고, 1부터 차례대로 섬에 대해 인덱싱을 해주기
2. 섬의수C2 인 조합을 이용하여 두개의 섬을 고르고, 가장 자리에 대해서 DFS를 이용하여 직선경로 찾기
3. 찾은 직선 경로에 대해 그래프의 형태를 만들기
4. 만든 그래프에 대해 모든 정점을 포함하며 정점보다 하나 적은 간선을 선택하게 되는 MST를 만들기
4-1. UnionFind를 이용한  간선 기준 Kruskal알고리즘 사용
4-2. PriorityQueue를 이용한 정점 기준 Prim 알고리즘 사용

다양한 알고리즘을 한번에 적용 시켜야 했던 문제이고, 여러가지를 다시 복습할 수 있어던 기회여서 좋은 문제라 생각한다.

 

Prim알고리즘 사용코드

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
import javax.naming.spi.DirStateFactory.Result;
 
public class Main_bj_17472_다리만들기2 {
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    
    //BFS변수
    static int R,C;
    static int[][] map;
    static int[][] mapNumbered;
    static boolean[][] visitForBFS;
    static int numbering;
 
    static Queue<Pos> queue;
    
    //Comb변수
    static int[] isLand;
    static int[] pick;
    static boolean[] visitForComb;
    
    
    static int answer;
    static int length;
    
    static class Pos{
        int i,j;
        
        Pos(int i,int j){
            this.i=i;this.j=j;
        }
    }
    
    
    //Prim 변수
    static List<Edge>[] list;
    static PriorityQueue<Edge> pq;
    static int[] distance;
    static boolean[] visitForPrim;
    
    
    static class Edge implements Comparable<Edge>{
        int point,weight;
        Edge(int p,int w) {
            point=p;weight=w;
        }
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(weight, o.weight);
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        map=new int[R][C];
        for(int i=0;i<R;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<C;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        numbering=0;
        visitForBFS=new boolean[R][C];
        mapNumbered=new int[R][C];
        queue=new LinkedList<>();
        bfsForNumbering();
        
//        for(int i=0;i<R;i++) {
//            for(int j=0;j<C;j++) {
//                System.out.print(mapNumbered[i][j]+" ");
//            }
//            System.out.println();
//        }
        
        
        isLand=new int[numbering];
        for(int i=0;i<numbering;i++)
            isLand[i]=i+1;
        
        visitForComb=new boolean[numbering];
        pick=new int[2];
    
        
        list=new ArrayList[numbering+1];
        for(int i=0;i<=numbering;i++)
            list[i]=new ArrayList<>();
        
        comb(0,0);
        
        
        distance=new int[numbering+1];
        for(int i=1;i<=numbering;i++)
            distance[i]=Integer.MAX_VALUE/2;
        
        
        visitForPrim=new boolean[numbering+1];
        pq=new PriorityQueue<>();
        prim(1);
 
        int answer=0;
        for(int i=1;i<=numbering;i++) {
            if(distance[i]==Integer.MAX_VALUE/2) {
                System.out.println(-1);
                return;
            }else{
                answer+=distance[i];
//                System.out.println(distance[i]);
            }
        }
        System.out.println(answer);
    }
 
 
    static void bfsForNumbering() {
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(map[i][j]==1 && visitForBFS[i][j]==false) {
                    numbering+=1;
                    queue.offer(new Pos(i, j));
                    visitForBFS[i][j]=true;
                    mapNumbered[i][j]=numbering;
                    
                    while(!queue.isEmpty()) {
                        Pos cur=queue.poll();
                        
                        for(int dir=0;dir<4;dir++) {
                            int nextI=cur.i+di[dir];
                            int nextJ=cur.j+dj[dir];
                            
                            if(nextI<0 ||nextI>=R ||nextJ<0 ||nextJ>=C)
                                continue;
                            if(map[nextI][nextJ]==1 && visitForBFS[nextI][nextJ]==false) {
                                visitForBFS[nextI][nextJ]=true;
                                queue.offer(new Pos(nextI, nextJ));
                                mapNumbered[nextI][nextJ]=numbering;
                            }
                            
                        }
                    }
                    
                }
            }
        }
    }
    
    static void comb(int start, int depth) {
        if(depth==2) {
            
            length=Integer.MAX_VALUE;
            for(int i=0;i<R;i++) {
                for(int j=0;j<C;j++) {
                    if(mapNumbered[i][j]==pick[0] && isSide(i, j)==true) {
                        dfs(i, j, pick[0], pick[1], -1, 0);
                    }
                }
            }
            if(length!=Integer.MAX_VALUE) {
                list[pick[0]].add(new Edge(pick[1], length));
                list[pick[1]].add(new Edge(pick[0], length));
//                System.out.println(pick[0]+","+pick[1]+"="+length);
            }
            
            
            return;
        }
        
        for(int i=start;i<numbering;i++) {
            if(visitForComb[i]==false) {
                visitForComb[i]=true;
                pick[depth]=isLand[i];
                comb(i,depth+1);
                visitForComb[i]=false;
            }
        }
    }
    
    static void dfs(int i,int j,int start,int dest, int d, int len) {
        if(d==-1) {    //초기시작
            for(int dir=0;dir<4;dir++) {
                int nextI=i+di[dir];
                int nextJ=j+dj[dir];
                
                if(nextI<0||nextI>=R ||nextJ<0 ||nextJ>=C)
                    continue;
                if(mapNumbered[nextI][nextJ]==0) 
                    dfs(nextI,nextJ,start,dest,dir,len+1);
                
            }
        }
        else {
            int nextI=i+di[d];
            int nextJ=j+dj[d];
            
            if(nextI<0||nextI>=R ||nextJ<0 ||nextJ>=C)
                return;
            
            if(mapNumbered[nextI][nextJ]==0) 
                dfs(nextI,nextJ,start,dest,d,len+1);
            
            if(mapNumbered[nextI][nextJ]==dest) {
                if(len!=1)
                    length=Math.min(len, length);
            }
                
            
        }
        
    }
    
    static boolean isSide(int i,int j) {
        for(int dir=0;dir<4;dir++) {
            int nextI=i+di[dir];
            int nextJ=j+dj[dir];
            
            if(nextI<0 ||nextI>=R|| nextJ<0 ||nextJ>=C)
                continue;
            
            if(mapNumbered[nextI][nextJ]==0)
                return true;
        }
        return false;
    }
 
    static void prim(int start) {
        distance[start]=0;
        
        pq.offer(new Edge(start, 0));
        
        while(!pq.isEmpty()) {
            Edge cur=pq.poll();
            
            if(visitForPrim[cur.point]==true)
                continue;
            
            for(Edge next : list[cur.point] ) {
                int dest =next.point;
                
                if(visitForPrim[dest]==false && distance[dest]>next.weight) {
                    distance[next.point]=next.weight;
                    pq.add(new Edge(next.point, next.weight));
                }
            }
            visitForPrim[cur.point] = true;
        }
    }
}