문제
N×N 지도에서 서로 다른 두 섬을 연결하는 가장 짧은 다리의 길이를 구하라.
입력
첫째 줄에 N, 이후 N줄에 지도(0: 바다, 1: 땅)가 주어진다.
출력
가장 짧은 다리의 길이를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 1 1 1 0 0 0 0 1 1 1 ... | 3 |
풀이
DFS로 섬에 번호를 부여하고, 모든 육지에서 동시 BFS로 바다를 확장하여 다른 섬과 만나는 최소 거리를 구한다.
- DFS로 각 섬에 고유 번호를 부여하고 모든 육지를 BFS 큐에 넣는다
- BFS로 바다를 한 칸씩 확장하며 섬 번호와 거리를 기록한다
- 인접한 칸이 다른 섬 번호이면 두 칸의 거리 합이 다리 길이이다
- 모든 경계에서 최솟값을 구한다
핵심 아이디어: 모든 육지에서 동시에 BFS를 수행하면 각 바다 칸까지의 최단 거리가 자연스럽게 구해진다.
코드
package day499;
import java.util.*;
import java.io.*;
public class Day469BOJ2146다리만들기 {
static boolean[][] visited;
static int[][] arr, len;
static int N, M, cnt;
static StringBuilder sb = new StringBuilder();
static Queue<int[]> q = new LinkedList<>();
static int[] dr = { -1, 0, 1, 0 }, dc = { 0, 1, 0, -1 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
visited = new boolean[N][N];
arr = new int[N][N];
len = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int no = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j] == 0 || visited[i][j])
continue;
no++;
dfs(i, j, no);
}
}
bfs();
int ans = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int d = 0; d < 4; d++) {
int nr = i + dr[d];
int nc = j + dc[d];
if (nr < 0 || nc < 0 || nr >= N || nc >= N || arr[i][j] == arr[nr][nc])
continue;
ans = Math.min(ans, len[i][j] + len[nr][nc]);
}
}
}
System.out.println(ans);
}
private static void dfs(int y, int x, int no) {
visited[y][x] = true;
arr[y][x] = no;
q.offer(new int[] { y, x });
for (int i = 0; i < 4; i++) {
int ny = y + dr[i];
int nx = x + dc[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] || arr[ny][nx] == 0)
continue;
dfs(ny, nx, no);
}
}
private static void bfs() {
while (!q.isEmpty()) {
int size = q.size();
cnt++;
for (int j = 0; j < size; j++) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nr = cur[0] + dr[i];
int nc = cur[1] + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N || arr[nr][nc] != 0)
continue;
q.offer(new int[] { nr, nc });
len[nr][nc] = cnt;
arr[nr][nc] = arr[cur[0]][cur[1]];
}
}
}
}
}복잡도
- 시간: O(N²)
- 공간: O(N²)