[백준] 2146. 다리 만들기

문제

 

---

풀이

먼저 각 섬을 구분하기 위해 1이 아닌 수(2,3,4...)로 초기화 시켜주었다. 그런 다음 각 섬마다 탐색을 진행함에 있어 시작 집합을 섬의 경계 (주위에 0이 존재하는 칸)를 잡고 다른 섬을 만나기 전까지 bfs를 수행하면서 최소거리를 구하는 방식으로 진행했다.

여기서 distance가 증가하는 시점에 대해서 고민을 많이 했는데 아래 코드처럼 BFS의 Level을 판단하기 위해 초기 bounday의 사이즈를 구하고 이에 대해서 반복문을 도는 방식으로 Level을 판단했다.

그리고 초기 풀이는 50%가 넘어갈 때 메모리 초과가 발생했는데, BFS를 수행할 때 visited를 체크하지 않아서 많은 중복이 발생했던 것이 문제였다. 그리고 visited를 갱신하는 위치가 current의 시점에서 할 수도 있고 next의 시점에서 할 수 있는데 확인 결과 next의 시점에서 체크하는 것이 효율적이어서 코드를 수정했다. 

최종 정답 코드는 다음과 같다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static class Pair {
		int x;
		int y;

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

		int first() {
			return x;
		}

		int second() {
			return y;
		}
	}

	private static int number = 2;
	private static int[] dx = { 0, 0, -1, 1 };
	private static int[] dy = { 1, -1, 0, 0 };

	public static void main(String[] args) {

		// input
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] map = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		// divide island
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if (map[i][j] == 1) {
					fillNumber(map, i, j);
					number++;
				}
			}
		}

		// get Minimum Distance
		int num = 2;
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if (map[i][j] == num) {
					min = Integer.min(min, getMinimumDistance(map, i, j));
					num++;
				}
			}
		}
		
		System.out.println(min);
	}

	private static void fillNumber(int[][] map, int x, int y) {
		boolean[][] visited = new boolean[map.length][map.length];
		Queue<Pair> sq = new LinkedList<Pair>();
		sq.add(new Pair(x, y));
		while (!sq.isEmpty()) {
			Pair current = sq.poll();
			map[current.first()][current.second()] = number;
			for (int i = 0; i < 4; i++) {
				int nextX = current.first() + dx[i];
				int nextY = current.second() + dy[i];

				if (nextX < 0 || nextX > map.length - 1 || nextY < 0 || nextY > map.length - 1
						|| map[nextX][nextY] != 1 || visited[nextX][nextY])
					continue;
				sq.add(new Pair(nextX, nextY));
				visited[nextX][nextY] = true;
			}
		}
	}

	private static int getMinimumDistance(int[][] map, int x, int y) {
		LinkedList<Pair> boundary = getBoundary(map, map[x][y]);
		boolean[][] visited = new boolean[map.length][map.length];
		int distance = 1;
		while (!boundary.isEmpty()) {
			int size = boundary.size();
			for (int i = 0; i < size; i++) {
				Pair current = boundary.poll();

				for (int idx = 0; idx < 4; idx++) {
					int nextX = current.first() + dx[idx];
					int nextY = current.second() + dy[idx];

					if (nextX < 0 || nextX > map.length - 1 || nextY < 0 || nextY > map.length - 1
							|| map[nextX][nextY] == map[x][y] || visited[nextX][nextY])
						continue;
					if (map[nextX][nextY] == 0) {
						visited[nextX][nextY] = true;
						boundary.add(new Pair(nextX, nextY));
					} else {
						return distance;
					}
					
				}
			}
			distance++;
		}
		return distance;
	}

	private static LinkedList<Pair> getBoundary(int[][] map, int num) {
		LinkedList<Pair> ret = new LinkedList<>();
		boolean[][] visited = new boolean[map.length][map.length];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if (map[i][j] != num)
					continue;
				for (int idx = 0; idx < 4; idx++) {
					int nextX = i + dx[idx];
					int nextY = j + dy[idx];

					if (nextX < 0 || nextX > map.length - 1 || nextY < 0 || nextY > map.length - 1 || visited[nextX][nextY])
						continue;
					if (map[nextX][nextY] == 0) {
						visited[nextX][nextY] = true;
						ret.add(new Pair(nextX, nextY));
					}
				}
			}
		}

		return ret;
	}

}