BOJ 2146 다리 만들기

메모리 : 80640 KB

시간 : 204 ms

BOJ 2146 다리 만들기 Gold 3

풀이

1. 섬들마다 숫자를 붙여 구분해준다.
2. 섬이 있는 부분이고 가장자리라면 다리를 설치한다.
3. 설치하다가 다른 번호의 섬을 만나면 설치를 중단하고 최소값인지 확인한다.

느낀점

BFS를 두 번 돌리는 문제였다.
나름 가지치기한다고

1. if (현재 섬의 번호 == 다음 섬의 번호) continue
2. if (현재 다리 길이 > 최소 다리 길이) break

등을 해봤는데 별 차이가 없었다..
그치만 시간을 줄일 방법을 생각해보는 건 좋은 현상인 것 같다!

코드

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

public class Main {
	static int N, min;
	static int[][] map;
	static boolean[][] visited;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visited = new boolean[N][N];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) map[i][j] = -1;
			}
		}
		
		// 각 섬을 구분해준다
		int num = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == -1 && !visited[i][j]) {
					numbering(i, j, num);
					num++;
				}
			}
		}
		
		min = Integer.MAX_VALUE;
		// 숫자를 가진 섬에서 가장자리인 부분에서 다리만들기를 시작한다
		// 다른 숫자를 가진 섬을 발견하면 길이를 확인한다
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > 0 && isEdge(i, j)) {
					makeBridge(i, j, map[i][j]);
				}
			}
		}
		
		System.out.println(min);
	}
	
	public static void makeBridge(int x, int y, int num) {
		visited = new boolean[N][N];
		Queue<Pos> q = new LinkedList<>();
		q.offer(new Pos(x, y));
		visited[x][y] = true;
		int length = -1;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int s = 0; s < size; s++) {
				Pos cur = q.poll();
				if (map[cur.x][cur.y] > 0 && map[cur.x][cur.y] != num) {
					min = Math.min(min, length);
					return;
				}
				for (int d = 0; d < 4; d++) {
					int nx = cur.x + dir[d][0];
					int ny = cur.y + dir[d][1];
					if (!isRange(nx, ny) || visited[nx][ny]) continue;
					q.offer(new Pos(nx, ny));
					visited[nx][ny] = true;
				}
			}
			length++;
		}
	}

	public static boolean isEdge(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if (!isRange(nx, ny)) continue;
			if (map[nx][ny] == 0) return true;
		}
		return false;
	}
	
	public static void numbering(int x, int y, int num) {
		Queue<Pos> q = new LinkedList<>();
		q.offer(new Pos(x, y));
		visited[x][y] = true;
		map[x][y] = num;
		
		while (!q.isEmpty()) {
			Pos cur = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = cur.x + dir[d][0];
				int ny = cur.y + dir[d][1];
				if (!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] == 0) continue;
				q.offer(new Pos(nx, ny));
				visited[nx][ny] = true;
				map[nx][ny] = num;
			}
		}
	}
	
	public static boolean isRange(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N) return true;
		else return false;
	}
	
	static class Pos {
		int x, y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}