[백준/2146/Java] 다리 만들기

 

문제:

www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

문제를 먼저 풀고 오시는 것을 추천합니다.
이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

 

 

문제분석

1은 땅이고, 0은 바다입니다.

먼저 땅을 연결하여 하나의 육지를 만들어야 합니다.

육지 간에 서로 다리를 놓아 가장 짧은 다리의 길이를 구하는 문제입니다.

 

 

입력

첫줄에 지도의 크기 N(0 < N <= 100)이 주어집니다.

그 다음 N개의 줄에 N개의 숫자가 주어집니다. (숫자 사이마다 사이에 공백이 있습니다.)

0은 바다, 1은 육지입니다.

항상 2개 이상의 섬이 있는 데이터만 주어집니다.

 

출력

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

 

 

풀이

단지번호붙이기(백준/2667번 문제)와 비슷하게 육지를 그룹으로 묶어서 번호를 매깁니다.

육지그룹 1개씩 시작하여 다른 육지그룹까지의 길이를 계산합니다.

단, 지금까지 알아낸 가장 짧은 다리의 길이보다 길면 더 이상 계산할 필요가 없습니다.

속도개선을 위한 일종의 가지치기입니다.

 

2차원 배열은 3개를 선언합니다.

첫번째 배열은 입력받은 값을 저장하는 배열입니다.

두번째 배열은 육지그룹을 저장하는 배열입니다.

세번째 배열은 다리길이를 계산하기 위한 배열입니다.

 

예제풀이

백준 문제에 있는 예제를 가지고 어떻게 동작하는지 확인해보겠습니다.

 

초기값

입력값을 첫번째 2차원 배열을 생성하고 값을 설정하면 이렇게 됩니다.

 

 

육지그룹 번호 매기기

육지그룹을 1부터 순서대로 번호를 매기고 두번째 2차원 배열에 저장합니다.

이 방법은 단지번호 붙이기 (백준/2667번 문제)와 같이 BFS로 모든 값에 대해서 진행하면 됩니다.

BFS가 종료되면 이렇게 됩니다.

 

다른 육지그룹까지의 다리 길이 계산하기

다른 육지그룹까지의 다리 길이를 계산하기 위하여 세번째 2차원 배열을 사용합니다.

두번째 2차원 배열을 참고하여

먼저 1번 육지그룹을 0으로 설정하고 그 외 모든 값들은 -1로 설정합니다.

그러면 1번 육지그룹은 이렇게 됩니다.

[0, 0, 0, -1, -1, -1, -1, -1, -1, -1]
[0, 0, 0, 0, -1, -1, -1, -1, -1, -1]
[0, -1, 0, 0, -1, -1, -1, -1, -1, -1]
[-1, -1, 0, 0, 0, -1, -1, -1, -1, -1]
[-1, -1, -1, 0, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

 

1번 육지그룹의 모든 육지를 큐에 넣고 BFS를 돌립니다.

그래서 0이 아닌 경우는 항상 기존 값에서 1씩 더하여 저장합니다.

그러면 이렇게 됩니다.

[0, 0, 0, 1, 2, 3, 4, 5, 6, 7]
[0, 0, 0, 0, 1, 2, 3, 4, 5, 6]
[0, 1, 0, 0, 1, 2, 3, 4, 5, 6]
[1, 1, 0, 0, 0, 1, 2, 3, 4, 5]
[2, 2, 1, 0, 1, 2, 3, 4, 5, 6]
[3, 3, 2, 1, 2, 3, 4, 5, 6, 7]
[4, 4, 3, 2, 3, 4, 5, 6, 7, 8]
[5, 5, 4, 3, 4, 5, 6, 7, 8, 9]
[6, 6, 5, 4, 5, 6, 7, 8, 9, 10]
[7, 7, 6, 5, 6, 7, 8, 9, 10, 11]

 

가장 짧은 다리의 길이를 구하기 위하여 첫번째 배열에서 땅인 부분을 비교하여 가장 작은 값을 찾습니다.

육지 부분은 색을 칠했고 값은 바로 위에서 구한 다리의 길이입니다. 

다리가 다른 육지를 만나기 바로 직전 값(노란색)인 3이 가장 짧은 길이입니다.

 

 

1번 육지가 종료되고 2번부터 다른 모든 육지까지 이와 같은 방법을 수행하면서 가장 짧은 다리 길이를 저장합니다.

단, 1번 육지에서 가장 짧은 다리의 길이를 3이라고 계산했기 때문에 다른 육지들을 계산할 때 3이 넘은 거리는 계산할 필요가 없어서 제외(BFS 큐에 안 넣기)하시면 속도가 빨라집니다.

 

 

소스

입력값을 저장하는 첫번째 배열은 A입니다.

육지그룹을 저장하는 두번째 배열은 M입니다.

다리 길이를 계산하여 저장하는 세번째 배열은 D입니다.

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

class Pair {
	int x;
	int y;

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

public class Main {
	public static final int[] dx = { 0, 0, 1, -1 };
	public static final int[] dy = { 1, -1, 0, 0 };
	
	public static int N;
	public static int[][] A;
	public static int[][] M;
	public static int[][] D;
	public static int ANS;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.valueOf(br.readLine());
		A = new int[N][N];
		M = new int[N][N];
		D = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				A[i][j] = Integer.valueOf(st.nextToken());
			}
		}
		
		// 육지 그룹
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (A[i][j] == 1 && M[i][j] == 0) {
					cnt++;
					bfs1(cnt, i, j);
				}
			}
		}

		// 육지 그룹 번호
//		print(M);
		
		ANS = -1;
		for (int l = 1; l <= cnt; l++) {
			Queue<Pair> q = new LinkedList<Pair>();
			// 동일육지그룹만 0으로 설정, 그 외 육지, 바다는 0
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					D[i][j] = -1;
					if (M[i][j] == l) {
						q.add(new Pair(i, j));
						D[i][j] = 0;
					}
				}
			}
//			print(D);
			while (!q.isEmpty()) {
				Pair p = q.remove();
				int x = p.x;
				int y = p.y;
				for (int k = 0; k < 4; k++) {
					int nx = x + dx[k];
					int ny = y + dy[k];
					if (0 <= nx && nx < N && 0 <= ny && ny < N) {
						if (D[nx][ny] == -1) {
							if (ANS != -1 && ANS < D[x][y]+1) continue;	// 현재까지 짧은 다리 길이보다 길면 계산하지 않는다.
							D[nx][ny] = D[x][y] + 1;
							q.add(new Pair(nx, ny));
						}
					}
				}
			}
//			print(D);
			// 가장 짧은 다리 길이 계산
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (A[i][j] == 1 && M[i][j] != l) {
						if ((ANS == -1 || D[i][j] - 1 < ANS) && D[i][j]>0) {	// 위에서 계산하지 않아서 -1인 값은 제외
							ANS = D[i][j] - 1;
						}
					}
				}
			}
		}
		System.out.println(ANS);
	}

	private static void print(int[][] a) {
		System.out.println();
		for (int i = 0; i < N; i++) {
			System.out.println(Arrays.toString(a[i]));
		}
	}

	private static void bfs1(int cnt, int i, int j) {
		Queue<Pair> q = new LinkedList<Pair>();
		M[i][j] = cnt;
		q.add(new Pair(i, j));
		while (!q.isEmpty()) {
			Pair p = q.remove();
			int x = p.x;
			int y = p.y;
			for (int k = 0; k < 4; k++) {	// 네방향 검색
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (0 <= nx && nx < N && 0 <= ny && ny < N) {
					if (A[nx][ny] == 1 && M[nx][ny] == 0) {
						q.add(new Pair(nx, ny));
						M[nx][ny] = cnt;
					}
				}
			}
		}
	}
}

 

관련글:

2021/03/05 - [Algorithm] - [백준/2667/Java] 단지번호붙이기

[백준/2667/Java] 단지번호붙이기