[BaekJoon] 2146 다리 만들기 (Java)

1.  문제 링크

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

2.  문제

요약

• 여러 섬으로 이루어진 나라가 있고 섬을 잇는 다리를 만드려고 합니다.
• 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 합니다.
• N x N 크기의 이차원 평면상에 나라가 존재하고 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말합니다.
• 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 하는데, 가장 짧은 다리란 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말합니다.
• 지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾는 문제입니다.
• 입력: 첫 번째 줄에 100보다 작거나 같은 자연수인 지도의 크기 N이 주어지고 두 번째 줄부터 N개의 줄에는 N개의 숫자가 주어집니다. 0은 바다, 1은 육지를 나타냅니다.
  • 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어집니다.
• 출력: 첫 번째 줄에 가장 짧은 다리의 길이를 출력합니다.

3.  소스코드

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

public class Main {
	static int N;
	static int[][] map;
	static boolean[][] visited;
	static HashMap<Integer, ArrayList<int[]>> edges;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		map = new int[N][N];
		visited = new boolean[N][N];
		edges = new HashMap<>();
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				int temp = scanner.nextInt();
				if(temp == 0) map[row][col] = 0;
				else if(temp == 1) map[row][col] = -1;
			}
		}
	}
	
	static void solution() {
		int landNum = 0;
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				if(!visited[row][col] && map[row][col] == -1) {
					landNum++;
					dfs(row, col, landNum);
				}
			}
		}
		for(int land = 1; land <= landNum; land++) edges.put(land, new ArrayList<int[]>());
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				if(map[row][col] != 0) {
					for(int dir = 0; dir < 4; dir++) {
						int cx = row + dx[dir];
						int cy = col + dy[dir];
						if(cx >= 0 && cx < N && cy >= 0 && cy < N) {
							if(map[cx][cy] == 0) {
								edges.get(map[row][col]).add(new int[] {row, col});
								break;
							}
						}
					}
				}
			}
		}
		int answer = Integer.MAX_VALUE;
		for(int land = 1; land <= landNum; land++) {
			for(int[] pos : edges.get(land)) {
				int dist = bfs(pos[0], pos[1], map[pos[0]][pos[1]]);
				answer = Math.min(answer, dist);
			}
		}
		System.out.println(answer);
	}
	
	static int bfs(int x, int y, int land) {
		Queue<int[]> queue = new LinkedList<>();
		int[][] dist = new int[N][N];
		for(int row = 0; row < N; row++) Arrays.fill(dist[row], Integer.MAX_VALUE);
		queue.add(new int[] {x, y});
		dist[x][y] = 0;
		int answer = Integer.MAX_VALUE;
		while(!queue.isEmpty()) {
			int[] pos = queue.poll();
			if(map[pos[0]][pos[1]] != 0 && map[pos[0]][pos[1]] != land) {
				answer = Math.min(answer, dist[pos[0]][pos[1]]) - 1;
				break;
			}
			for(int dir = 0; dir < 4; dir++) {
				int cx = pos[0] + dx[dir];
				int cy = pos[1] + dy[dir];
				if(cx >= 0 && cx < N && cy >= 0 && cy < N && dist[cx][cy] == Integer.MAX_VALUE) {
					if(map[cx][cy] != land) {
						dist[cx][cy] = dist[pos[0]][pos[1]] + 1;
						queue.offer(new int[] {cx, cy});
					}
				}
			}
		}
		return answer;
	}
	
	static void dfs(int x, int y, int landNum) {
		visited[x][y] = true;
		map[x][y] = landNum;
		for(int dir = 0; dir < 4; dir++) {
			int cx = x + dx[dir];
			int cy = y + dy[dir];
			if(cx >= 0 && cx < N && cy >= 0 && cy < N && !visited[cx][cy]) {
				if(map[cx][cy] == -1) dfs(cx, cy, landNum);
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}