[backjoon]2146 다리 만들기 java

www.acmicpc.net/problem/2146

2146번: 다리 만들기

gold 3

bfs 두번 사용해서 풀었다.

1. 여러 섬들을 구분한다. (dfs나 bfs이용해서 구분, 나의 경우엔 어차피 다 연결되어있는 거라 판단해서 bfs를 사용하였다.)

2. 바다이며(0인 경우), 주변에 섬인 경우(1인 경우) 다른 섬과의 거리를 파악한다.(최단 거리를 파악해야하기에 bfs를 이용한다.) 거리 배열을 따로 두어 거리를 파악하였다.(예전엔 무턱대고 cnt로 하였는데 이렇게하면 값이 어마어마하게 커질 수 있어서 거리 계산은 꼭 배열을 이용해서 이전 값보다 1씩 커지게끔 해줘야한다.)

3. 최소 값을 리턴한다.

주의 사항 섬에서 섬을 못 찾아가는 경우를 생각해 리턴 값을 잘 선정해야 한다. -> 나의 경우 여기서 헤맸다.

몇 날 며칠 풀이를 고민했던 건데 섬이 아닌 바다를 기준으로 풀이하였더니 비교적 쉽게 풀렸다.

 

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

class Main {
	static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	static int[][] intiMap, numberingMap;
	static boolean[][] visited;
	static int N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		intiMap = new int[N][N];
		numberingMap = new int[N][N];
		visited = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int temp = Integer.parseInt(st.nextToken());
				intiMap[i][j] = temp;
			}
		}
		
		int number = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (intiMap[i][j] == 1 && !visited[i][j]) 
					numberingBfs(i, j, number++);
			}
		}
		
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (numberingMap[i][j] == 0) {
					//주변 중 하나가 0(바다)이 아닌지 확인하기.
					int aroundNumber = aroundSearch(i, j);
					if (aroundNumber == 0) continue;
					
					visited = new boolean[N][N];
					int distance = settingDistance(i, j, aroundNumber);
					min = Math.min(min, distance);
				}
			}
		}
		
		if(min == Integer.MAX_VALUE) min = 0;
		System.out.println(min);
	}
	
	//섬간 거리 파악하기, 다른 섬을 찾으면 바로 리턴한다. 
	//섬을 못 찾으면 최대 값을 리턴한다.(우리가 찾아야하는 값은 최소값이기 때문에 큰 값을 넣어줘서 못 찾았음을 구분해야 함)
	public static int settingDistance(int row, int col, int ignoreNumber) {
		Queue<Dot> queue = new LinkedList<Dot>();
		queue.add(new Dot(row, col));
		int[][] distance = new int[N][N];

		while (!queue.isEmpty()) {
			
			Dot cur = queue.poll();
			
			for (int i = 0; i < 4; i++) {
				int nextRow = cur.row + dir[i][0];
				int nextCol = cur.col + dir[i][1];
				
				if (nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= N) continue;
				if (numberingMap[nextRow][nextCol] == ignoreNumber || visited[nextRow][nextCol]) continue;
				if (numberingMap[nextRow][nextCol] != 0) return distance[cur.row][cur.col] +1;
				
				visited[nextRow][nextCol] = true;
				queue.add(new Dot(nextRow, nextCol));
				distance[nextRow][nextCol] = distance[cur.row][cur.col] +1;
			}
		}
		return Integer.MAX_VALUE;
	}
	
	//섬 근처의 바다인지 확인.
	public static int aroundSearch(int row, int col) {
		
		for (int i = 0; i < 4; i++) {
			int nextRow = row + dir[i][0];
			int nextCol = col + dir[i][1];
			
			if (nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= N) continue;
			if (numberingMap[nextRow][nextCol] != 0) return numberingMap[nextRow][nextCol];
		}
		
		return 0;
	}
	
	//섬을 구분하기 위해 숫자 붙이기.
	public static void numberingBfs(int row, int col, int number) {
		Queue<Dot> queue = new LinkedList<Dot>();
		queue.add(new Dot(row, col));
		numberingMap[row][col] = number;
		
		while (!queue.isEmpty()) {
			Dot cur = queue.poll();
			
			for (int i = 0; i < 4; i++) {
				int nextRow = cur.row + dir[i][0];
				int nextCol = cur.col + dir[i][1];
				
				if (nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= N) continue;
				if (visited[nextRow][nextCol] || intiMap[nextRow][nextCol] != 1) continue;
				
				visited[nextRow][nextCol] = true;
				numberingMap[nextRow][nextCol] = number;
				queue.add(new Dot(nextRow, nextCol));
			}
		}
	}
}

class Dot{
	int row;
	int col;
	Dot(int row, int col){
		this.row = row;
		this.col = col;
	}
}