[Baekjoon] 2146_다리 만들기

Gold III

문제(출처: https://www.acmicpc.net/problem/2146)

---

< 다리 만들기 >

 

문제 풀이 

 

같은 섬 영역을 먼저 찾는다. 섬 하나를 다 찾았다면 가장자리 부분들만 bfs를 사용해서 다른 섬까지의 최단 거리를 찾아주는 방법으로 문제를 해결했다.

 

 

 my solution (Java)

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

public class _2146_ { // 다리 만들기
	static int arr[][], n, result;
	static boolean visited[][];
	static Queue<int[]> land;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

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

		n = Integer.parseInt(bf.readLine());
		arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		visited = new boolean[n][n];
		land = new LinkedList<>();
		result = -1;

		int idx = 2;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[i][j] == 1) {
					arr[i][j] = idx;
					findLand(i, j, idx);
					bfs();
					init();
					idx += 1;
				}
			}
		}
		System.out.println(result);

	}

	private static void findLand(int i, int j, int idx) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			boolean flag = false;
			for (int k = 0; k < 4; k++) {
				int x = temp[0] + dx[k];
				int y = temp[1] + dy[k];
				if (x >= 0 && x < n && y >= 0 && y < n) {
					if (arr[x][y] == 1) {
						arr[x][y] = idx;
						queue.add(new int[] { x, y });
					} else if (arr[x][y] == 0 && !flag) {
						land.add(new int[] { temp[0], temp[1], arr[temp[0]][temp[1]], 0 });
						flag = true;
					}
				}
			}
		}
	}

	private static void bfs() {
		boolean flag = false;

		while (!land.isEmpty()) {
			int temp[] = land.poll();
			for (int i = 0; i < 4; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < n && y >= 0 && y < n && !visited[x][y] && arr[x][y] != temp[2]) {
					if (arr[x][y] != 0) {
						if (result == -1 || result > temp[3]) {
							result = temp[3];
						}
						flag = true;
						break;

					}
					visited[x][y] = true;
					land.add(new int[] { x, y, temp[2], temp[3] + 1 });
				}
			}
			if (flag) {
				land.clear();
				break;
			}
		}
	}

	private static void init() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				visited[i][j] = false;
			}
		}
	}
}

 

Main

변수)
n : 지도의 크기
arr : 지도 정보
vistied: 방문 여부
land : 섬의 가장자리 위치 정보 저장 queue [x, y, 섬 번호, 거리]
result : 다리 길이
idx : 섬 번호
queue : 같은 섬 찾기 위해 정보 저장 queue [x, y]

 

- 지도의 크기 (n) 입력 및 지도의 정보(arr) 입력

- 지도 전체를 탐색

: 같은 섬 찾기

: 하나의 섬을 다 찾은 후 섬의 가장자리에서 다른 섬으로의 가장 짧은 거리 찾기

: 방문 표시(visited) 초기화

- 가장 짧은 다리 길이(result) 출력

 

findLand

- queue에 저장 [x좌표, y좌표]

- queue가 빌 때까지 반복

: 상하좌우로 이동하여 지도 범위 안이라면 

1) 같은 섬이라면 섬 번호 저장 및 queue에 추가

2) 바다라면 섬의 가장자리란 뜻이므로 land 큐에 추가

 

bfs

- land가 빌 때까지 반복

: 상하좌우로 이동하여 지도 범위 안이며 아직 방문하지 않았고 같은 섬이 아니라면

1) 다른 섬이라면 다리 길이 최솟값으로 업데이트 및 종료

2) 바다라면 방문 표시 및 land 큐에 추가

* 종료할 때 land 큐 값 초기화 주의!

 

init

- 방문표시 배열 값 초기화

---

---