[Java] 백준 2146번. 다리 만들기 (골드4)

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

2146번: 다리 만들기

구현을 신경써야 하는 문제입니다.

문제를 2개의 과정으로 나눌 수 있습니다.

 

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 다리 만들기

 

1번은 BFS DFS아무것이나 원하는 방법으로 구현하면 됩니다.

2번의 경우는 BFS를 이용하는것이 구현과 이해가 간편합니다.

시간 단축을 위해서는 모든 경우에 대해 다리를 구하고 다리의 길이를 비교하는 것 보다는 최소값을 다리가 완성될 때 마다 갱신하고, 이미 구해진 최솟값을 넘는 경우에는 Queue를 비워버리고 스킵하는 것이 훨씬 빠릅니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q2146_BOJ_다리만들기 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;
	static int[] parent;
	static int N;

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

		N = Integer.parseInt(br.readLine());

		map = new int[N][N];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < N; m++) {
				if (map[n][m] == -1) {
					dfs(n, m, island);
					island++;
				}
			}
		}

		int answer = Integer.MAX_VALUE;
		Queue<int[]> queue = new LinkedList<>();
		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][N];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < N; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m });
						visit[n][m] = true;
					}
				}
			}

			int l = 0;

			while (!queue.isEmpty()) {
				int size = queue.size();

				for (int s = 0; s < size; s++) {

					int[] now = queue.poll();
					int x = now[0];
					int y = now[1];

					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY]) {

							if (map[nX][nY] == 0) {
								queue.offer(new int[] { nX, nY });
								visit[nX][nY] = true;
							} else {
								answer = Math.min(answer, l);
								visit[nX][nY] = true;
							}
						}
					}
				}
				l++;
				if (l > answer) {
					queue.clear();
				}
			}
		}
		System.out.println(answer);

	}

	static void dfs(int x, int y, int name) {
		map[x][y] = name;

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY) && map[nX][nY] == -1) {
				dfs(nX, nY, name);
			}
		}

	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N) {
			return true;
		}
		return false;
	}
}