[JAVA]백준2146번 다리 만들기

문제는 다음과 같다.

오늘은 백준2146번 다리 만들기 문제를 풀어보도록 하자. 각 섬이 있다면 섬마다 다리를 이어 연결시켜주어야 하는데 그 다리 중 가장 짧은 다리를 구하는 문제이다.

예전에 C++로 풀어보았지만 JAVA로 풀어보고 싶어 다시 푼 문제이다. 우선 떨어져있는 섬을 이어줘야 하는데 구분이 되지 않게 섬들은 다 1로 되어있다. 따라서 섬을 구분해주기 위해 그룹핑을 해서 섬의 넘버링을 해주었다.

1번섬, 2번섬, 3번섬 등등.. 넘버링을 해주고 난 뒤 최단거리 를 구해야하는 문제이므로 BFS를 써주었다. 만일 DFS로 푼다면 최악의 경우 시간 복잡도가 O(4^10000)으로 어마무시하게 측정이 될 것이다.

main함수에서 2중포문으로 섬의 일부분에서 출발한 뒤 다른 섬에 도달했다면 값비교를 통해 최솟값을 알아내고 큐 안에 값들을 다 빼주고 리턴하였다.

그리 어려운 문제는 아니였다.

                                     [코드]
import java.awt.*;
import java.io.*;
import java.util.*;

public class Main {
    static int N,num=1,answer=987654321;
    static boolean visit[][];
    static int map[][];
    static int dir[][] = { {-1,0},{0,1},{1,0},{0,-1} };

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

        N = Integer.parseInt(br.readLine());
        visit = new boolean[N][N];
        map = new int[N][N];

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //섬 구분
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j] && map[i][j] != 0){
                    Island_num(i,j);
                    num++;
                }
            }
        }
        //방문 초기화
        Init_visit();
        //다리만들기
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j] && map[i][j] != 0){
                    Make_bridge(i,j,map[i][j]);
                    Init_visit();
                }
            }
        }
        System.out.println(answer);
    }
    public static void Island_num(int y, int x){
        Queue<Point>Q = new LinkedList<Point>();
        visit[y][x] = true;
        Q.offer(new Point(y,x));
        map[y][x] = num;

        while(!Q.isEmpty()){
            int ny = Q.peek().x;
            int nx = Q.peek().y;
            Q.poll();

            for(int i=0;i<4;i++){
                int my = ny + dir[i][0];
                int mx = nx + dir[i][1];

                if(my>=0 && mx>=0 && my<N && mx<N){
                    if(!visit[my][mx] && map[my][mx] == 1){
                        visit[my][mx] = true;
                        map[my][mx] = num;
                        Q.offer(new Point(my,mx));
                    }
                }
            }
        }
    }
    public static void Make_bridge(int y, int x, int start){
        Queue<pos_cnt>Q = new LinkedList<pos_cnt>();
        Q.offer(new pos_cnt(y,x,0));
        visit[y][x] = true;

        while(!Q.isEmpty()){
            int ny = Q.peek().y;
            int nx = Q.peek().x;
            int cnt = Q.peek().cnt;

            Q.poll();

            for(int i=0;i<4;i++){
                int my = ny + dir[i][0];
                int mx = nx + dir[i][1];

                if(my>=0 && mx>=0 && my<N && mx<N){
                    if(!visit[my][mx]){
                        if(map[my][mx] == 0){
                            visit[my][mx] = true;
                            Q.offer(new pos_cnt(my,mx,cnt+1));
                        }
                        else if(map[my][mx] != 0 && map[my][mx] != start){
                            answer = Math.min(answer, cnt);
                            Q.clear();
                            return;
                        }
                    }
                }
            }
        }
    }
    public static void Init_visit(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                visit[i][j] = false;
            }
        }
    }
}
class pos_cnt{
    int y;
    int x;
    int cnt;
    
    pos_cnt(int y, int x, int cnt){
        this.y = y;
        this.x = x;
        this.cnt = cnt;
    }
}