[백준]JAVA - 2146번: 다리 만들기

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

2146번: 다리 만들기

🔶 풀이

"섬에서 섬으로 건너갈 수 있는 가장 짧은 다리의 길이는?"

 

가장 먼저 해야할 건 각각의 섬에 다른 번호를 매겨주는 것이다.

여러 개의 섬이 존재하는데 번호가 같으면 bfs를 이용해서 다른 섬을 찾아가는 게 힘들다.

public static void setLand (int x, int y, int num) {
    Queue<Pos> q = new LinkedList<>();
    q.add(new Pos(x, y, 0));
    visited[x][y] = true;
        
    while (!q.isEmpty()) {
        Pos now = q.poll();
        map[now.x][now.y] = num; 
            
        boolean flag = false;
        for (int d=0; d<4; d++) {
            int nx = now.x + dx[d];
            int ny = now.y + dy[d];
                
            if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1) continue;
                
            if (!flag && map[nx][ny] == 0) {
                edges.add(now);
                flag = true;
            }
                
            if (!visited[nx][ny] && map[nx][ny] == 1) {
                q.add(new Pos(nx, ny, 0));
                visited[nx][ny] = true;
            }
        }
    }
}

(0, 0)부터 시작해서 아직 방문하지 않은 섬을 발견했을 때, num 값을 증가시켜주면서 섬에 번호를 매긴다. 

 

또한, 위 과정에서 섬의 모서리를 edges 배열리스트에 입력해준다.

바다와 하나라도 맞닿은 부분이 있다면 모서리라고 간주하고 입력해주는데 flag 변수를 이용해서 중복을 막아줬다.

 

 

섬의 번호를 매겨줬으면 다음 과정은 쉽다.

이것 또한 bfs를 이용해 모서리에서 다음 섬의 번호에 도달할 때까지 돌려주면 된다.

그 중에서 가장 낮은 값을 출력해주면 끝.

 

<최종코드>

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

public class Main {
    static int[] dx = {1, 0 , -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, ans = Integer.MAX_VALUE;
    static int[][] map;
    static boolean[][] visited;
    static ArrayList<Pos> edges = new ArrayList<>(); 
    
    public static class Pos {
        int x, y, len;
        
        public Pos (int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[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 num = 1;
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    setLand(i, j, num++);
                }
            }
        }
        
        for (Pos eg : edges) {
            makeBrige(eg.x, eg.y, map[eg.x][eg.y]);
        }
        
        System.out.println(ans);
    }
    
    public static void setLand (int x, int y, int num) {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(x, y, 0));
        visited[x][y] = true;
        
        while (!q.isEmpty()) {
            Pos now = q.poll();
            map[now.x][now.y] = num; 
            
            boolean flag = false;
            for (int d=0; d<4; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];
                
                if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1) continue;
                
                if (!flag && map[nx][ny] == 0) {
                    edges.add(now);
                    flag = true;
                }
                
                if (!visited[nx][ny] && map[nx][ny] == 1) {
                    q.add(new Pos(nx, ny, 0));
                    visited[nx][ny] = true;
                }
            }
        }
    }
    
    public static void makeBrige (int x, int y, int land) {
        Queue<Pos> q = new LinkedList<>();
        visited = new boolean[N][N];
        
        q.add(new Pos(x, y, 0));
        visited[x][y] = true;
        
        while (!q.isEmpty()) {
            Pos now = q.poll();
            
            if (now.len >= ans) return;
            
            for (int d=0; d<4; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];
                
                if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1) continue;
                
                if (map[nx][ny] != land && map[nx][ny] != 0) {
                    ans = Math.min(ans, now.len);
                    return;
                }
                
                if (!visited[nx][ny] && map[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.add(new Pos(nx, ny, now.len+1));
                }
            }
        }
    }
}