[BOJ] 2146. 다리 만들기

두번의 BFS를 이용하였다.

첫번째 BFS로 각 섬마다 번호를 지정해주었고, isEdge라른 함수를 이용하여 현재 위치가 가장 자리인 것이 확인이 되면 두번째 BFS를 사용하여 다른 섬까지의 거리를 구해주는 방식으로 해결하였다.

package chap05;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_2146_다리만들기 {
    
    static int N;
    static int[][] island;
    static int[][] map;
    static boolean[][] visit;
    
    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};
    
    static Queue<Pos> queue;
    
    static int islandNumber=0;
    static int result;
    
    static class Pos{
        int i,j;
        int dis;
        public Pos(int i,int j) {
            this.i=i;this.j=j;dis=0;
        }
        public Pos(int i,int j, int d) {
            this.i=i;this.j=j;dis=d;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        visit=new boolean[N][N];
        map=new int[N][N];
        island=new int[N][N];
        queue= new LinkedList<>();
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        bfsFindIsland();        //맵별로 만듬
 
        result=Integer.MAX_VALUE;
        bfsFindDis();
        System.out.println(result);
//        for(int i=0;i<N;i++) {
//            for(int j=0;j<N;j++) {
//                System.out.print(island[i][j] +" ");
//            }
//            System.out.println();
//        }
        
    }
    
    static boolean isEdge(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 >=N || nextJ<0 || nextJ>=N)
                continue;
            if(map[nextI][nextJ]==0)
                return true;
        }
        return false;
    }
    
    static void bfsFindIsland() {
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(map[i][j]==1 && visit[i][j]==false) {
                    islandNumber++;
                    queue.offer(new Pos(i, j));
                    visit[i][j]=true;
                    island[i][j]=islandNumber;
                    
                    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 >=N || nextJ<0 || nextJ>=N)
                                continue;
                            
                            if(map[nextI][nextJ]==1 && visit[nextI][nextJ]==false) {
                                visit[nextI][nextJ]=true;
                                island[nextI][nextJ]=islandNumber;
                                queue.offer(new Pos(nextI, nextJ));
                            }
                        }
                    }
                    
                }
            }
        }
    }
    
    static void bfsFindDis() {
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(island[i][j]!=0 && isEdge(i, j)==true) {
                    visit=new boolean[N][N];
                    queue.offer(new Pos(i, j,0));
                    int landNum=island[i][j];
                    
//                    System.out.println(i+","+j+"="+landNum);
                    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 >=N || nextJ<0 || nextJ>=N)
                                continue;
                            
 //바다인 경우
                            if(island[nextI][nextJ]==0 && visit[nextI][nextJ]==false) {
                                visit[nextI][nextJ]=true;
                                queue.offer(new Pos(nextI, nextJ, cur.dis+1));
                            }
 
                          //육지인 경우
                            if(island[nextI][nextJ]!=0 && island[nextI][nextJ]!=landNum) {
//                                visit[nextI][nextJ]=true;
//                                System.out.print(nextI+","+nextJ+" = "+cur.dis +" >> ");
                                result=Math.min(result, cur.dis);
                            }
                        }
                    }
                }
//                System.out.println();
                
            }
        }
        
        
    }
}