[백준 2146번] 다리 만들기 :: 늦깎이 IT

[백준 2146번] 다리 만들기 URL

1. 각 섬마다 번호를 매긴다 (2, 3, 4, ....)

2. 그리고 모든 섬들을 큐에 넣어주고 BFS를 돌린다. BFS를 돌릴 때 다음 칸이 0이라는 뜻은 바다라는 뜻이므로

해당 섬의 번호로 땅을 확장한다.

3. 다음 칸이 0도 아니고, 현재 위치의 땅 번호와도 다르다면, 다른 땅이 그곳까지 확장됐다는 뜻이므로 거리를 계산한다.

4. 거리를 계산하는 방법은 dist라는 2차원 배열을 따로 만들고 BFS 탐색을 할 때 땅이 한 칸 확장되었다면 거리또한 1씩 증가시키는 것이다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, ans = Integer.MAX_VALUE;
    static int[][] map;
    static int[][] dist;
 
    static int[] dirX = new int[] { 0, 0, 1, -1 };
    static int[] dirY = new int[] { 1, -1, 0, 0 };
 
    static Queue<Node> q;
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
        dist = new int[N][N];
        q = new LinkedList<>();
 
        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 idx = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    setLand(i, j, idx++);
                }
            }
        }
        solve();
        System.out.println(ans);
    }
 
    public static void solve() {
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int land = node.land;
 
            for (int i = 0; i < 4; i++) {
 
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc)) {
 
                    if (map[nr][nc] == 0) {
 
                        map[nr][nc] = land;
                        dist[nr][nc] = dist[row][col] + 1;
                        q.offer(new Node(nr, nc, land));
 
                    } else if (map[nr][nc] != land && map[nr][nc] != 0) {
                        ans = Math.min(ans, dist[nr][nc] + dist[row][col]);
                    }
                }
            }
        }
    }
 
    public static void setLand(int row, int col, int land) {
 
        Queue<Node> temp = new LinkedList<>();
        temp.offer(new Node(row, col, land));
 
        while (!temp.isEmpty()) {
 
            Node node = temp.poll();
            map[node.row][node.col] = land;
            q.offer(node);
 
            for (int i = 0; i < 4; i++) {
 
                int nr = node.row + dirX[i];
                int nc = node.col + dirY[i];
 
                if (isBoundary(nr, nc) && map[nr][nc] == 1) {
                    map[nr][nc] = land;
                    temp.offer(new Node(nr, nc, land));
                }
            }
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
}
 
class Node {
    int row;
    int col;
    int land;
 
    public Node(int row, int col, int land) {
        this.row = row;
        this.col = col;
        this.land = land;
    }
 
}