처음 이 문제를 그냥 BFS로 풀려고 하니 답이 안나왔다. 왜냐하면 대륙1, 대륙2, 대륙3은 서로 다른 대륙이기에 동시에 진행해버리면 서로 서로에게 가까워지면서 실제 시간보다 빠르게 나오기때문이다. 독립적인 실행이 가능하게 해야했다. 즉, 대륙1에서만 BFS를 진행하고 그다음엔 대륙2에서 BFS를 진행하는.. 식으로 해야했다
그런데.. 한대륙에서만 bfs를 진행한다고 하더라도 다른 좌표(r,c)에서의 bfs 진행 결과가 현재 좌표 (x,y)에 영향을 미치면 제대로 된 결과가 안나올 것 같았다.

문제상황

static int bfs(int r, int c,int cnt){
        int result=0;
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r,c));
        while(!q.isEmpty()){
            int size = q.size();
            while(size>0){
                Point cur = q.poll();
                visited[cur.r][cur.c] = true;

                for(int i=0;i<4;i++){
                    int rr = cur.r + dx[i];
                    int cc = cur.c + dy[i];
                    if(rr>=n||cc>=n||rr<0||cc<0||visited[rr][cc]) continue;
                    if(map[rr][cc]==0){
                        visited[rr][cc] = true;
                        q.add(new Point(rr,cc));
                    }else if(map[rr][cc] == cnt){
                        visited[rr][cc] = true;
                    }else{
                        return result;
                    }

                }

                size--;
            }
            result++;
        }
        return -1;

    }
  //main함수
   for(int i =0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(map[i][j] == 0||visited[i][j]) continue;
                min = Math.min(min,bfs(i,j,map[i][j]));
            }
        }

• 메인함수내에서의 이중 포문은 내가 걱정했던 문제를 해결해준다
• 하나의 좌표에 대해 bfs를 수행하면서 다른 좌표에서 수행한 bfs 좌표랑 격리해주는것같다
• bfs함수에서는 탐색이 다끝나면 -1을 return하는데 이 값을 처음에 return하도록 한 이유는 제대로 값을 못찾으면 값을 구분하기 위해서였다. 하지만 bfs가 여러번 실행되고, 하나의 케이스에서는 좌표가 내륙에 위치해서 더이상 탐색을 안할수도있다. 그럼 -1 이 return될거고 그럼 제대로 된 min값이 안나온다

정답코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static int n;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static int map[][];
    static boolean visited[][];
    static int bfs(int r, int c,int cnt){
        int result=0;
        visited = new boolean[n][n];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r,c));
        while(!q.isEmpty()){
            int size = q.size();
            while(size>0){
                Point cur = q.poll();
                visited[cur.r][cur.c] = true;

                for(int i=0;i<4;i++){
                    int rr = cur.r + dx[i];
                    int cc = cur.c + dy[i];
                    if(rr>=n||cc>=n||rr<0||cc<0||visited[rr][cc]) continue;
                    if(map[rr][cc]==0){
                        visited[rr][cc] = true;
                        q.add(new Point(rr,cc));
                    }else if(map[rr][cc] == cnt){
                        visited[rr][cc] = true;
                    }else{
                        return result;
                    }

                }

                size--;
            }
            result++;
        }
        return Integer.MAX_VALUE;

    }
    //map에 있는 대륙의 개수를 count한다
    static int count(){
        temp = new boolean[n][n];
        int result = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(!temp[i][j] && map[i][j]==1) {
                    dfs(i,j, ++result);
                }
            }
        }
        return result;
    }
    static void dfs(int r, int c, int k){
        temp[r][c] = true;
        map[r][c] = k;
        for(int i=0;i<4;i++){
            int rr = r + dx[i];
            int cc = c + dy[i];
            if(rr>=n||cc>=n||rr<0||cc<0||temp[rr][cc] ||map[rr][cc]==0) continue;
            dfs(rr,cc, k);
        }
    }
    static class Point{
        int r;
        int c;
        Point(int r, int c){
            this.r=r;
            this.c=c;
        }
    }
    static boolean temp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        for(int i=0;i<n;i++) {
            String input2[]= br.readLine().split(" ");
            for(int j=0;j<n;j++) {
                map[i][j] = Integer.parseInt(input2[j]);
            }
        }
        //각섬을 섬1, 섬2, 섬3으로 구분한다
        count();
        int min = Integer.MAX_VALUE;
        for(int i =0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(map[i][j] == 0) continue;
                //한점에 대해서 bfs 탐색을한다
                //한점에 대해서만 탐색하니 여러 점에 의한 탐색 충돌이 안발생한다
                min = Math.min(min,bfs(i,j,map[i][j]));
            }
        }
        //가장 짧은 다리 출력
        System.out.println(min);


    }

}

메모리를 많이 사용하는 문제

정답으로 처리가 되긴했지만 다른 풀이에 비해 메모리를 많이 사용하고 있었다
추가적으로 방문배열을 하나 더 선언해서 내가 탐색한 대륙1에 대해 모두 방문처리를 해주는 식으로 코드를 짜면 메모리를 반절정도 덜 사용하게 된다

//main
 temp = new boolean[n][n];
        for(int i =0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(map[i][j] == 0||temp[i][j]) continue;
                //한점에 대해서 bfs 탐색을한다
                //한점에 대해서만 탐색하니 여러 점에 의한 탐색 충돌이 안발생한다
                temp[i][j] = true;
                min = Math.min(min,bfs(i,j,map[i][j]));
            }
        }
    

static int bfs(int r, int c,int cnt){
        //한점에서만 bfs를 진행할거기때문에 visited배열을 매번 초기화 해주어야한다
        temp[r][c] = true;
        visited = new boolean[n][n];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r,c,0));
        while(!q.isEmpty()){
            //size 만큼 반복해주는 행위 = class에 len이라는 필드추가하는것과 같음
            Point cur = q.poll();
            //1x1의 예외상황을 처리하기 위함
            visited[cur.r][cur.c] = true;

            for(int i=0;i<4;i++){
                int rr = cur.r + dx[i];
                int cc = cur.c + dy[i];
                if(rr>=n||cc>=n||rr<0||cc<0||visited[rr][cc]) continue;
                //방문안한 점인데 0이면 그쪽으로 탐색을 진행한다. 그러다가 다른 지역을 만나면 result(time) 을 반환한다
                if(map[rr][cc]==0){
                    visited[rr][cc] = true;
                    q.add(new Point(rr,cc,cur.t+1));
                    //map[rr][cc]가 0 도 아니고 cnt도 아니라면 다른 대륙이다
                    //time의 최소시간을 return해주자
                }else if(map[rr][cc] != cnt){
                    return cur.t;
                }else{
                   //추가 이거때문에 ..
                   temp[rr][cc] = true;
                }

            }
        }
        return Integer.MAX_VALUE;

    }