문제
https://www.acmicpc.net/problem/2146
N x N 격자에서 1은 땅(섬), 0은 바다다.
서로 다른 두 섬을 잇는 다리를 만들 때, 지나는 바다 칸의 최소 개수를 구하면 된다.
다리는 상하좌우로만 연결되고, 섬 내부 칸은 다리 길이에 포함되지 않는다.
풀이 과정
기본 알고리즘은 완전탐색으로 하면 된다.
- 각 섬 구분하기(섬 라벨링)
BFS로 연결된 육지를 한 덩이로 묶어서 1, 2, 3, ... 같은 번호를 붙인다.
// 섬을 구분한 새로운 배열 만들기
island = new int[N][N];
visited = new boolean[N][N];
int count = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] != 0 && !visited[i][j]) {
bfs(count, i, j);
count += 1;
}
}
}같은 섬을 찾는 bfs
private static void bfs(int count, int i, int j) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] { i, j });
visited[i][j] = true;
island[i][j] = count;
while (!q.isEmpty()) {
int[] curr = q.poll();
int x = curr[0];
int y = curr[1];
for (int k = 0; k < 4; k++) {
int nx = x + di[k];
int ny = y + dj[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && board[nx][ny] == 1) {
visited[nx][ny] = true;
island[nx][ny] = count;
q.offer(new int[] { nx, ny });
}
}
}
}
- 섬을 개수만큼 돌면서 출발지와 도착지의 번호가 다르면 다른 섬이라는 의미이기 때문에, 그때마다 거리를 구하고 최소거리를 갱신해준다.
int minPath = Integer.MAX_VALUE;
// 섬의 개수만큼 돌면서 길이를 구하기
// 맨허튼 거리 구하기
for (int m = 1; m <= count; m++) {
// m번째 섬의 출발점을 다 구하기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (island[i][j] == m) {
// 출발지에서 도착지까지
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (island[x][y] != m && island[x][y] != 0) {
// 거리 구하기
int currPath = manhattan(i, j, x, y);
// 최소거리 업데이트
minPath = Integer.min(minPath, currPath);
}
}
}
}
}
}
}
System.out.println(minPath -1);
}최소거리를 구하는 방법은 맨허튼 거리 방식을 쓰면 편하다.
public static int manhattan(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}전체코드
package backjoon;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class 다리만들기_2146 {
static int N;
static int[][] board;
static int[][] island;
static boolean[][] visited;
static int[] di = { -1, 1, 0, 0 };
static int[] dj = { 0, 0, -1, 1 };
public static void main(String[] args) throws NumberFormatException, IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
board = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// 각 섬의 테두리를 섬 번호로 적기
// 육지라면 -1을 넣기
// 섬을 구분한 새로운 배열 만들기
island = new int[N][N];
visited = new boolean[N][N];
int count = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] != 0 && !visited[i][j]) {
bfs(count, i, j);
count += 1;
}
}
}
int minPath = Integer.MAX_VALUE;
// 섬의 개수만큼 돌면서 길이를 구하기
// 맨허튼 거리 구하기
for (int m = 1; m <= count; m++) {
// m번째 섬의 출발점을 다 구하기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (island[i][j] == m) {
// 출발지에서 도착지까지
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (island[x][y] != m && island[x][y] != 0) {
// 거리 구하기
int currPath = manhattan(i, j, x, y);
// 최소거리 업데이트
minPath = Integer.min(minPath, currPath);
}
}
}
}
}
}
}
System.out.println(minPath -1);
}
private static void bfs(int count, int i, int j) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] { i, j });
visited[i][j] = true;
island[i][j] = count;
while (!q.isEmpty()) {
int[] curr = q.poll();
int x = curr[0];
int y = curr[1];
for (int k = 0; k < 4; k++) {
int nx = x + di[k];
int ny = y + dj[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && board[nx][ny] == 1) {
visited[nx][ny] = true;
island[nx][ny] = count;
q.offer(new int[] { nx, ny });
}
}
}
}
public static int manhattan(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
}
피드백
완전탐색 + 맨허튼 거리
주의할 점
이 방식은 장애물(다른 섬)을 고려하지 않아 최단 경로가 막힐 수 있다. 즉, 맨해튼 최소가 실제로 못 가는 거리일 수 있다.
완전탐색+맨해튼: 최악 O(N⁴)라 입력이 크면 부담된다.
N=100에서도 최악에선 꽤 느리다.
다른 아이디어 : “섬 테두리”에서 바다로 BFS
각 섬의 테두리 칸(옆에 바다가 있는 육지)만 시작점으로 잡는다.
그 테두리에서 바다로 BFS를 돌리다가 다른 섬의 육지를 처음 만나면, 그때의 거리가 해당 섬과의 최소 다리 길이다.
섬마다 반복해서 전역 최소를 갱신한다.
시간복잡도
섬별 BFS 1회가 O(N²) 근처, 최악 섬 수가 많아도 N ≤ 100이라 충분히 통과한다.
static int N;
static int[][] board; // 입력(0/1)
static int[][] island; // 라벨링 결과(0=바다, >=1 섬번호)
static boolean[][] visited;
static int[] di = {-1, 1, 0, 0};
static int[] dj = {0, 0, -1, 1};
static boolean isBorder(int i, int j) {
if (island[i][j] == 0) return false;
for (int d = 0; d < 4; d++) {
int ni = i + di[d], nj = j + dj[d];
if (0 <= ni && ni < N && 0 <= nj && nj < N && island[ni][nj] == 0) {
return true;
}
}
return false;
}
static int bfsMinBridgeFromIsland(int id) {
// 거리배열: -1 미방문, 육지(start)는 0으로 시작
int[][] dist = new int[N][N];
for (int i = 0; i < N; i++) java.util.Arrays.fill(dist[i], -1);
java.util.ArrayDeque<int[]> q = new java.util.ArrayDeque<>();
// 1) 출발점: 해당 섬의 "테두리 육지"만 큐에 넣기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (island[i][j] == id && isBorder(i, j)) {
dist[i][j] = 0;
q.offer(new int[]{i, j});
}
}
}
// 2) 바다로 확장하는 BFS
int best = Integer.MAX_VALUE;
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
// 현재까지의 거리로 이미 최적을 넘겼으면 가지치기
if (dist[x][y] >= best) continue;
for (int d = 0; d < 4; d++) {
int nx = x + di[d], ny = y + dj[d];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
// 같은 섬 육지로는 확장할 필요 없음
if (island[nx][ny] == id) continue;
// 바다면 다리를 1칸 더 늘려서 전진
if (island[nx][ny] == 0) {
if (dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.offer(new int[]{nx, ny});
}
}
// 다른 섬을 만났다면 현재까지 바다칸 수(dist[x][y])가 다리 길이
else { // island[nx][ny] != 0 && island[nx][ny] != id
best = Math.min(best, dist[x][y]);
}
}
}
return best;
}
static int solveMinBridge() {
// 1) 섬 라벨링 완료돼 있다고 가정 (island[][] 채워짐)
// 2) 섬 id마다 BFS 돌려서 최소 갱신
int maxId = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
maxId = Math.max(maxId, island[i][j]);
}
}
int answer = Integer.MAX_VALUE;
for (int id = 1; id <= maxId; id++) {
answer = Math.min(answer, bfsMinBridgeFromIsland(id));
}
return answer;
}