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

문제

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

풀이

• N*N 크기의 나라
• 나라는 여러 섬으로 이루어져 있음
• 섬이란 동서남북으로 육지가 붙어있는 덩어리
• 1: 육지, 0: 바다
• 서로 다른 섬을 잇는 가장 짧은 다리의 길이 출력

주어진 각 섬을 그룹화하여, 다른 섬까지의 길이가 가장 짧은 것을 출력하는 문제입니다.
BFS를 이용하여 각 섬을 그룹화 후, 다른 섬까지의 길이를 구했습니다.

입력

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

• n: 길이
• map: 지도의 정보

섬 그룹화

grouping()

	private static void grouping() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 1) {
					groupBfs(i, j);
					label++;
				}
			}
		}
	}

• 만약 그룹화가 되지 않은 섬일 경우 BFS를 이용해 그룹화를 진행하였습니다.
• label: 섬의 번호

groupBfs()

	private static void groupBfs(int sr, int sc) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { sr, sc });
		map[sr][sc] = label;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
				if (map[nr][nc] == 1) {
					map[nr][nc] = label;
					queue.add(new int[] { nr, nc });
				}
			}
		}
	}

• 시작 지점부터 하여, 인접한 모든 칸을 label로 채웠습니다.

다리 건설

build()

	private static void build() {
		answer = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] > 1) {
					buildBfs(i, j, map[i][j]);
				}
			}
		}
	}

• 만약 탐색하는 칸이 섬이라면 BFS 시작
• 파라미터는 시작 좌표와 다리를 짓기 시작하는 섬의 번호를 보냈습니다.

buildBfs()

	private static void buildBfs(int sr, int sc, int start) {
		Queue<int[]> queue = new ArrayDeque<>();
		boolean[][] visited = new boolean[n][n];
		
		queue.add(new int[] { sr, sc, 0 });
		visited[sr][sc] = true;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1], len = cur[2];
			
			if (len > answer) continue; // 가지치기
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc]) continue;
				
				if (map[nr][nc] == 0) {
					visited[nr][nc] = true;
					queue.add(new int[] { nr, nc, len + 1 });
					continue;
				}
				
				if (map[nr][nc] != start) {
					answer = Math.min(answer, len);
				}
			}
		}
	}

• 큐를 생성하고 큐에 시작 좌표와 길이 0을 넣어 줍니다.
• 만약 다음 좌표가 바다일 경우 방문 처리 후, 큐에 좌표와 함께 (현재 길이 + 1) 값을 넣어 줍니다.
• 만약 다음 좌표가 다른 섬일 경우에 최소길이를 업데이트합니다.

출력

		System.out.println(answer);

• 탐색이 끝났으면 최종적으로 업데이트된 값을 출력합니다.

코드

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

public class Main_2146 {
	static int n, answer;
	static int[][] map;
	
	static int label = 2;
	
	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	
	private static void grouping() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 1) {
					groupBfs(i, j);
					label++;
				}
			}
		}
	}
	
	private static void groupBfs(int sr, int sc) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { sr, sc });
		map[sr][sc] = label;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1];
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
				if (map[nr][nc] == 1) {
					map[nr][nc] = label;
					queue.add(new int[] { nr, nc });
				}
			}
		}
	}
	
	private static void build() {
		answer = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] > 1) {
					buildBfs(i, j, map[i][j]);
				}
			}
		}
	}
	
	private static void buildBfs(int sr, int sc, int start) {
		Queue<int[]> queue = new ArrayDeque<>();
		boolean[][] visited = new boolean[n][n];
		
		queue.add(new int[] { sr, sc, 0 });
		visited[sr][sc] = true;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1], len = cur[2];
			
			if (len > answer) continue;
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc]) continue;
				
				if (map[nr][nc] == 0) {
					visited[nr][nc] = true;
					queue.add(new int[] { nr, nc, len + 1 });
					continue;
				}
				
				if (map[nr][nc] != start) {
					answer = Math.min(answer, len);
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		grouping();
		build();
		
		System.out.println(answer);

	}

}