[백준] 2146번 : 다리 만들기

문제

 

 

접근 방식

1이 끊어지지 않고 최대로 이어진 곳들을 하나의 대륙이라고 볼 수 있고

각 대륙들을 서로 잇는 다리의 길이들을 구해야 한다.

 

일단 각 대륙들을 구분하면서 각 대륙의 외곽 지역을 큐들에 집어넣었는데

대륙의 외곽 지역은 바다와 맞닿아 있는 땅이라고 볼 수 있다.

 

외곽 지역을 모두 찾은 후에는 외곽을 순회하면서

바다만 찾아서 탐색을 하면서 다른 대륙을 마주친 경우

현재까지 이동한 거리를 이전의 다리 길이와 비교하여

더 작은 경우에는 값을 바꿔주었다.

 

풀이 자체는 쉽게 떠올렸는데 코드로 구현하고 보니 엄청 길어진...

 

풀이

public class Main {

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

		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};

		int n = Integer.parseInt(br.readLine());

		int[][] maps = new int[n][n];
		boolean[][] isVisited = new boolean[n][n];
		boolean[][] isWall = new boolean[n][n];

		int count = 0;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int num = Integer.parseInt(st.nextToken());
				maps[i][j] = num;
				count = Math.max(count, num);
			}
		}

		int area = 1;
		Queue<Continent> continents;
		Queue<Continent> walls = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!isVisited[i][j] && maps[i][j] == 1) {
					continents = new LinkedList<>();
					continents.offer(new Continent(i, j));
					isVisited[i][j] = true;
					maps[i][j] = area;

					while (!continents.isEmpty()) {
						Continent cur = continents.poll();

						for (int dir = 0; dir < 4; dir++) {
							int x = cur.x + dx[dir];
							int y = cur.y + dy[dir];

							if (x < 0 || x >= n || y < 0 || y >= n) continue;
							if (isVisited[x][y]) continue;
							if (maps[x][y] == 0) {
								if (!isWall[cur.x][cur.y]) {
									isWall[cur.x][cur.y] = true;
									walls.offer(cur);
								}
								continue;
							}

							isVisited[x][y] = true;
							maps[x][y] = area;
							continents.offer(new Continent(x, y));
						}
					}

					area++;
				}
			}
		}

		int distance = Integer.MAX_VALUE;
		Queue<Continent> queue;

		while (!walls.isEmpty()) {
			Continent wall = walls.poll();
			int continent = maps[wall.x][wall.y];
			queue = new LinkedList<>();
			isVisited = new boolean[n][n];
			wall.dist = 0;
			queue.offer(wall);
			isVisited[wall.x][wall.y] = true;

			while (!queue.isEmpty()) {
				Continent cur = queue.poll();

				for (int dir = 0; dir < 4; dir++) {
					int x = cur.x + dx[dir];
					int y = cur.y + dy[dir];

					if (x < 0 || x >= n || y < 0 || y >= n) continue;

					int next = maps[x][y];
					if (next == continent || isVisited[x][y]) continue;
					if (next != 0) {
						distance = Math.min(distance, cur.dist);
						continue;
					}
					if (cur.dist >= distance) {
						isVisited[x][y] = true;
						continue;
					}

					isVisited[x][y] = true;
					queue.offer(new Continent(x, y, cur.dist + 1));
				}
			}

		}
		System.out.println(distance);
	}

	private static class Continent {
		int x;
		int y;
		int dist;

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

		public Continent(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}
}