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

 

2146번: 다리 만들기

제가 사용한 방법은 처음에 BFS로 라벨링을 했습니다.

그리고 그 라벨마다 따로 BFS를 돌려주어 다른 섬을 만나면 거리를 구해

최소값 구하기 연산을 하여서 각 섬에서의 최소거리를 비교하였습니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<int[]> Q = new LinkedList<>();
        int[] dx = new int[]{1, 0, -1, 0};
        int[] dy = new int[]{0, 1, 0, -1};
        int n = Integer.parseInt(br.readLine());
        String[][] field = new String[n][n];
        boolean[][] visited = new boolean[n][n];

        for (int i=0; i<n; i++)
            field[i] = br.readLine().split(" ");

        int num = 0;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++){
                if (visited[i][j] || field[i][j].equals("0")) continue;
                num++;
                field[i][j] = Integer.toString(num);
                visited[i][j] = true;
                Q.offer(new int[]{i, j});
                while (!Q.isEmpty()){
                    int[] cur = Q.poll();
                    for (int dir=0; dir<4; dir++){
                        int nx = cur[1] + dx[dir];
                        int ny = cur[0] + dy[dir];
                        if (nx<0 || nx>=n || ny<0 || ny>=n) continue;
                        if (visited[ny][nx] || field[ny][nx].equals("0")) continue;
                        field[ny][nx] = Integer.toString(num);
                        visited[ny][nx] = true;
                        Q.offer(new int[]{ny, nx});
                    }
                }
            }

//        for (String[] f : field){
//            for (String d : f)
//                System.out.print(d+" ");
//            System.out.println();
//        }

        int min = Integer.MAX_VALUE;

        for(int f=1; f<=num; f++){
            int[][] dist = new int[n][n];
            for (int i=0; i<n; i++)
                Arrays.fill(dist[i], -1);
            for (int i=0; i<n; i++)
                for (int j=0; j<n; j++)
                    if (Integer.parseInt(field[i][j])==f) {
                        Q.offer(new int[]{i, j});
                        dist[i][j] = 0;
                    }
            while (!Q.isEmpty()){
                int[] cur = Q.poll();
                for (int dir=0; dir<4; dir++){
                    int nx = cur[1] + dx[dir];
                    int ny = cur[0] + dy[dir];
                    if (nx<0 || nx>=n || ny<0 || ny>=n || dist[ny][nx]>=0) continue;
                    if (!field[ny][nx].equals("0") && Integer.parseInt(field[ny][nx])!=f) {
                        min = Math.min(min, dist[cur[0]][cur[1]]);
                        Q.clear();
                    }
                    dist[ny][nx] = dist[cur[0]][cur[1]] + 1;
                    Q.offer(new int[]{ny, nx});
                }
            }
        }
        System.out.print(min);
    }
}