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

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

2146번: 다리 만들기

문제

풀이

탐색 문제이다. 우선 섬의 갯수를 세고 각 섬마다 다른 숫자로 라벨링을 해준다. (초기1-> 2,3,4, .... )
섬 아무곳에서 출발하여 바다면 움직인거리+1 다른 섬을만나면 섬<->섬 거리 최소거리 갱신

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
 
public class Main {
    static int N,landNum,minDepth;
    static int[][] map;
    static int[] dx,dy;
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        init();
        for(int i=0;i<N;i++)
            map[i] = Arrays.stream(br.readLine().split(" ")).
                    mapToInt(Integer::parseInt).toArray();
        findLand();
//        print();
        search();
        System.out.println(minDepth);
 
    }
 
    static void findLand() {
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++) if(map[i][j]==1) makeLandNumber(new Point(j,i));
    }
 
    static void makeLandNumber(Point p){
        LinkedList<Point> queue = new LinkedList<>();
        ++landNum;
        map[p.y][p.x]=landNum;
        queue.add(p);
        while (!queue.isEmpty()){
            Point cur = queue.poll();
            for(int i=0;i<4;i++){
                int nextX = dx[i] + cur.x;
                int nextY = dy[i] + cur.y;
 
                if(isRange(nextX, nextY) && map[nextY][nextX] == 1) {
                    queue.add(new Point(nextX,nextY));
                    map[nextY][nextX]=landNum;
                }
            }
        }
    }
    static void search() {
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++) if(map[i][j]>1) makeBridge(new Point(j,i,0));
    }
 
    static void makeBridge(Point p) {
        visit = new boolean[N][N];
        LinkedList<Point> queue = new LinkedList<>();
        queue.add(p);
        visit[p.y][p.x] = true;
        while (!queue.isEmpty()){
            Point cur = queue.poll();
            for(int i=0;i<4;i++){
                int nextX = dx[i] + cur.x;
                int nextY = dy[i] + cur.y;
 
                if(isRange(nextX, nextY) && !visit[nextY][nextX] && map[nextY][nextX] != map[p.y][p.x]) {
                    visit[nextY][nextX] = true;
                    if(map[nextY][nextX]==0) queue.add(new Point(nextX,nextY,cur.depth+1)); //바다일때
                    else minDepth = Math.min(minDepth,cur.depth); //다른 섬에 도착 했을 때
                }
            }
        }
    }
 
    static void print(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++) System.out.print(map[i][j]+" ");
            System.out.println();
        }
    }
    static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<N&&y<N;
    }
    static void init(){
        map = new int[N][N];
        visit = new boolean[N][N];
        dx = new int[] {0,0,1,-1};
        dy = new int[] {1,-1,0,0};
        landNum=1;
        minDepth=Integer.MAX_VALUE;
    }
    static class Point{
        int x,y;
        int depth;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        public Point(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
 
        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", depth=" + depth +
                    '}';
        }
    }
}