문제 - 다리만들기

문제접근

1. 섬 구분 및 번호 매기기 (0 : 바다 1: 섬)
   • 섬의 번호는 2부터 시작
   • bfs를 이용하여 번호 매기기
2. 각 섬의 가장자리에서부터 시작해서 다른 섬까지의 최단 거리를 bfs로 구하기

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static int map[][] ;
    static int N;
    static int dx[]= {0,1,0,-1};
    static int dy[]= {1,0,-1,0};
    static boolean visit[][];
    public static void main(String[] args) throws  Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        visit = new boolean[N][N];
        map = new int[N][N];

        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());
            }
        }
        int number= 2;
        //섬 구분 및 번호 매기기
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] == 1 && !visit[i][j]){
                    setIsland(i,j,number++);
                }
            }
        }

        //각 섬에 최단거리 계산
        int minV = Integer.MAX_VALUE;
        for(int i=2;i<number;i++)
        {
            minV = Math.min(minV,bfsMinDistance(i));
        }
        System.out.println(minV);
    }
    //섬의 가장자리에서 시작해서 다른 섬까지의 거리를 구함
    private static int bfsMinDistance(int island) {
        Queue<int[]> queue = new LinkedList<>();
        boolean visited[][] = new boolean[N][N];

        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(map[i][j] == island)
                {
                    queue.offer(new int[]{i,j,0});
                    visited[i][j] = true;
                }
            }
        }

        while(!queue.isEmpty())
        {
            int[] cur = queue.poll();

            for(int d=0;d<4;d++)
            {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];

                if(0<= nx && nx<N && 0<= ny && ny<N)
                {
                    //다른 섬을 만난 경우
                    if(map[nx][ny] > 0 && map[nx][ny] != island){
                        return cur[2];
                    }
                    //이동할 수 있는 곳
                    if(map[nx][ny] == 0 && visited[nx][ny] == false)
                    {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx,ny,cur[2]+1});
                    }
                }
            }
        }
        return Integer.MAX_VALUE;
    }

    private static void setIsland(int x, int y,int number) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x,y});
        visit[x][y] = true;
        map[x][y] = number;

        while(!queue.isEmpty()){

            int cnt[] = queue.poll();

            for(int d=0;d<4;d++){
                int nx = cnt[0] + dx[d];
                int ny = cnt[1] + dy[d];

                if(0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny]){
                    if(map[nx][ny] == 0) continue;
                    queue.offer(new int[]{nx,ny});
                    map[nx][ny] = number;
                    visit[nx][ny] = true;
                }
            }
        }

    }
}