[Java] BOJ2146, 백준 - 다리 만들기

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

2146번: 다리 만들기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	192MB	24895	8861	5566	33.321%

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

 

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

 

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

 

<풀이>

한 섬에서 다른 섬으로 가는 경로를 구해야 하기 때문에, 첫 번째로 해야할 것은 주어진 입력을 연결 요소별로 그룹화하는 것이다.

두 번째로는 각 연결요소 별 최소 거리를 구하면 된다.

 

주어진 지도의 연결 요소를 구하는 것, 그리고 다른 연결 요소까지의 최소 거리를 구하는 것 모두 BFS를 이용하면 쉽게 구할 수 있다.

 

다만, 한 가지 주의할 점이 있는데 이것 때문에 시간을 엄청 잡아먹었다.

연결 요소를 구할 때 BFS방식으로 진행되기 때문에, 최솟값을 구하는지 여부와 상관없이 큐에 들어가는 순서대로 거리가 구해지게 된다.

즉, 처음으로 두 섬을 잇는 경로를 찾았다고 해서 그게 최솟값이 되지는 않는다. 이 점을 주의하고 코드를 작성하자

 

소스코드

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

public class Main {

	private static int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	private static int n;
	private static int[][] d;
	private static int[][] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		Queue<Point> land = new LinkedList<Point>();
		Queue<Point> queue = new LinkedList<Point>();
		arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			// land로부터 시작
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 1)
					land.add(new Point(j, i));
			}
		}

		int group = 1;
		// 각 섬별로 그룹 번호를 매긴다.
		d = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 한 번도 방문하지 않은 점이라면 새로운 섬(그룹)
				if (arr[i][j] != 0 && d[i][j] == 0) {
					// 새로운 섬으로부터 BFS를 수행
					arr[i][j] = group;
					d[i][j] = 1;
					queue.add(new Point(j, i));
					bfs(group++, queue);
				}
			}
		} // 그룹화 완료

		int min = 1000;

		// 이제 BFS를 이용해 섬들 사이의 최소 거리를 구해보자
		while (!land.isEmpty()) {
			int size = land.size();

			for (int i = 0; i < size; i++) {
				int x = land.peek().x;
				int y = land.peek().y;
				group = arr[y][x];

				for (int j = 0; j < 4; j++) {
					int nx = x + move[j][0];
					int ny = y + move[j][1];

					if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
						if (arr[ny][nx] == 0) {
							d[ny][nx] = d[y][x] + 1;
							arr[ny][nx] = group;
							land.add(new Point(nx, ny));
						} else if (arr[ny][nx] != group) {
							// 답을 찾았을 때 종료해버리면 큐에 들어가는 순서로 인해서 최솟값을 찾는 것을 보장할 수 없음을 주의하자
							min = Math.min(min, d[y][x] + d[ny][nx] - 2);
						}
					}
				}
				land.poll();
			}
		}
        // 최솟값이 바뀌지 않았다는 것은 BFS를 수행하지 않았다는 의미(섬이 하나밖에 없음을 의미)
		if (min == 1000)
			System.out.println(0);
		else
			System.out.println(min);
	}

	private static void bfs(int group, Queue<Point> queue) {
		while (!queue.isEmpty()) {
			int x = queue.peek().x;
			int y = queue.peek().y;

			for (int i = 0; i < 4; i++) {
				int nx = x + move[i][0];
				int ny = y + move[i][1];

				if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
					if (d[ny][nx] == 0 && arr[ny][nx] != 0) {
						d[ny][nx] = 1;
						arr[ny][nx] = group;
						queue.add(new Point(nx, ny));
					}
				}
			}
			queue.poll();
		}
	}
}

class Point {
	int x, y;

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