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

2146번: 다리 만들기

---

[BFS]

크루스칼을 이용한 '다리 만들기 2'와 비슷한 문제.

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

먼저 입력받은 지도를 Labeling(BFS)을 통해 연결된 섬 별로 나누어준다. 섬은 2개 이상 나오게 된다. 한 번의 BFS를 했으면 다시 BFS를 할 차례이다. 각 섬의 모든 구역에서 BFS를 실시한다. 단, 최소 값(min)을 정하여 탐색을 진행하다가 값이 min을 초과하면 탐색을 중지하도록 하여 자원 소모를 줄인다.

 

> BFS의 과정

현재 정점에서 다음 상하좌우가 갈 수 있는 곳으로 판단되면,

다음 지역이 '0'이면 거리를 1만큼 늘린 값을 큐에 좌표와 함께 넣는다.

다음 지역이 '다른 섬'이면 min을 현재 거리로 변경한다.

 

# Code </>

public class Main {

    static class Point{
        int y, x, d;
        public Point(int yy, int xx){
            y=yy; x=xx;
        }
        public Point(int yy, int xx, int dd){
            this(yy, xx);
            d=dd;
        }
    }
    static final int N = 101;
    static boolean[][] visit = new boolean[N][N];
    static int[][] map = new int[N][N];

    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int min = 1000000000;

    static void labeling(int n){
        Queue<Point> Q = new LinkedList<>();
        int area = 0;
        int[][] label = new int[N][N];

        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++){
                if(!visit[i][j] && map[i][j] == 1){
                    area++;
                    visit[i][j] = true;
                    label[i][j] = area;
                    Q.add(new Point(i, j));
                }
                while(!Q.isEmpty()){
                    Point p = Q.poll();

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

                        if(ny < 1 || nx < 1 || ny > n || nx > n || visit[ny][nx] || map[ny][nx] == 0) continue;

                        label[ny][nx] = area;
                        visit[ny][nx] = true;
                        Q.add(new Point(ny, nx));
                    }
                }
            }
        map = label.clone();
    }
    static void BFS(int n){

        Queue<Point> Q = new LinkedList<>();

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

                int current = map[i][j];
                visit = new boolean[N][N];

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

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

                    int y = p.y;
                    int x = p.x;
                    int d = p.d;

                    if(d > min) continue;

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

                        if(ny < 1 || nx < 1 || ny > n || nx > n || visit[ny][nx] || map[ny][nx] == current) continue;

                        visit[ny][nx] = true;

                        if(map[ny][nx] == 0)
                            Q.add(new Point(ny, nx, d + 1));
                        else
                            min = Math.min(min, d);
                    }
                }
            }
    }

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

        int n = Integer.parseInt(br.readLine());

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

        labeling(n);
        BFS(n);

        System.out.println(min);
    }
}