[백준 2146] 다리 만들기

생각 정리

두 대륙을 연결하는 가장 짧은 다리 구하기
1. 서로 다른 대륙임을 어떻게 구분하는가
서로 다른 대륙임을 나타내는 배열을 하나 만든다.
2. 서로 다른 대륙임을 나타내는 배열에서 bfs를 진행. 일단 상하좌우 탐색했을 때 같은 숫자만 있으면 그냥 리턴(=다른 숫자가 하나라도 있으면 리턴x) / 다른 숫자를 만날떄까지 탐색해가기

• 방문했으면 넘어가기
• 현재 위치가 바다가 아니고, 서로 다른 대륙인 경우 현재까지의 거리를 리턴하기

생각하지 못한것

• 육지일때 bfs를 진행한다. (처음엔 바다일 때 bfs를 진행했다.)
• 현재 위치와 탐색을 시작한 위치가 같은 경우 넘어가주어야 한다.
• 현재 위치가 바다가 아니고, 서로 다른 대륙인 경우 현재까지의 최소거리를 구하고 리턴한다.
• 하나의 대륙에서 탐색이 끝나면 방문여부를 다시 초기화해주어야 한다.

코드

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

class Position{
    int x;
    int y;
    
    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


public class Main{
    /*
     * 두 대륙을 연결하는 가장 짧은 다리 구하기
        1. 서로 다른 대륙임을 어떻게 구분하는가
            서로 다른 대륙임을 나타내는 배열을 하나 만든다. 
        2. 서로 다른 대륙임을 나타내는 배열에서 bfs를 진행. 일단 상하좌우 탐색했을 때 같은 숫자만 있으면 그냥 리턴(이 아니고 넘어가) || 이미 방문했으면 넘어가 || 배열의 범위를 벗어나면 넘어가 / 다른 숫자를 만날떄까지 탐색해가기

     */
    static int N, min = Integer.MAX_VALUE;
    static int[][] map, dist;
    static boolean[][] visited;
    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];
        dist = new int[N][N];
        visited = new boolean[N][N];

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int idx = 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == 1 && !visited[i][j]){
                    makeIsland(i, j, idx);
                    idx++;
                }
            }
        }   


        //방문여부 초기화
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                visited[i][j] = false;
            }
        }

            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(map[i][j] != 0){
                        bfs(i, j);
                    }
                }
            }

        System.out.println(min);


    }

    static void makeIsland(int x, int y, int idx) {
        Queue<Position> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        queue.add(new Position(x, y));
        visited[x][y] = true;
        map[x][y] = idx;

        while(!queue.isEmpty()) {
            Position out = queue.poll();
            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx<0 || ny<0 || nx >=N || ny >=N) continue;
                else if(visited[nx][ny] || map[nx][ny] == 0) continue;
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                    map[nx][ny] = idx;
                }
            }
        }
    }

    static void bfs(int x, int y) { //육지를 무시해야하는거 아닐까 ,, (즉, 육지인 경우 그냥 넘어가) 바다인 경우만 탐색을 하다가 (거리를 구해가면서) (잔짜 아님,, 바다가 아닐 때 탐색) 육지를 만났을 때, 다른 육지라면, map[nx][ny] != 0 && map[x][y] != map[nx][ny] 일 때 그 최소거리를 구하는 것.. 
        Queue<Position> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        queue.add(new Position(x, y));
        visited[x][y] = true;

        while(!queue.isEmpty()) {
            Position out = queue.poll();

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

                if(nx<0 || ny<0 || nx >=N || ny >=N) continue;
                else if(visited[nx][ny] || map[x][y] == map[nx][ny]) continue; 
                else if(map[nx][ny] != 0 && map[x][y] != map[nx][ny]) {
                    min = Math.min(min, dist[out.x][out.y]);
                    //방문여부 초기화
                    for(int k=0; k<N; k++) {
                        for(int j=0; j<N; j++) {
                            visited[k][j] = false;
                        }
                    }
                    return ;
                }
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[out.x][out.y] + 1;
                }
            }

        }
        
        //방문여부 초기화
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                visited[i][j] = false;
            }
        }
    }
}

해당 풀이보다 시간복잡도를 낮추어서 풀 수 있는 방법도 있다고 한다.
더 공부하고 다시 정리해야겠다 !