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

https://www.acmicpc.net/problem/2146

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    static int n;
    static int[][] arr;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] visit;
    static int min = Integer.MAX_VALUE;
    static class Point{
        int x, y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        visit = new boolean[n][n];

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visit[i][j] && arr[i][j] ==1){ // 방문하지 않은 땅이라면
                    visit[i][j] = true;
                    cnt++;
                    arr[i][j] = cnt; // 땅에 숫자 부여
                    divideLand(i, j, cnt);
                }

            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j] !=0){
                    visit = new boolean[n][n];
                    visit[i][j] = true;
                    getDistance(i, j, arr[i][j]);
                }
            }
        }
        System.out.println(min);
    }
    static void getDistance(int x, int y, int landIdx){
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y));
        int[][] dis = new int[n][n];

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

            for(int i=0; i<4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];

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

                visit[nx][ny] = true;
                if(arr[nx][ny] == 0){ // 바다면
                    dis[nx][ny] = dis[p.x][p.y] + 1; // 거리 갱신
                    q.offer(new Point(nx, ny));
                }else if(arr[nx][ny] != landIdx){ // 바다가 아니고 다른 육지라면
                    min = Math.min(min, dis[p.x][p.y]); // 최소 거리 찾기
                }
            }
        }
    }
    static void divideLand(int x, int y, int cnt){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));

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

            for(int i=0; i<4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];

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

                if(arr[nx][ny] == 1){ // 땅이라면
                    arr[nx][ny] = cnt; // 당에
                    visit[nx][ny] = true;
                    q.offer(new Point(nx, ny));
                }
            }
        }

    }
}

 

 

땅을 구분하기 위해 bfs를 호출하고, 땅과 땅 사이의 최단 거리를 찾기위해 또 다른 bfs를 호출했다.

모든 좌표를 돌면서 땅이라면 bfs를 호출하고 바다를 만나면 거리를 한칸씩 갱신한다.

그리고 자신이 아닌 다른 땅을 만나는 순간 땅에서 땅까지의 거리의 최솟값을 구해나간다.