백준 - 2146번 다리 만들기 - java

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

 

접근법

나누어진 육지의 개수가 정해진게 아니라, 중심이 되는 섬과 그렇지 않은 섬으로 구분하는 방식으로 접근함
1. 방문하지 않은 섬의 좌표하나를 통해, bfs로 그 섬의 구분자를 2 로 변경
2. 새로 만들어진 newMap과 시작 시 다리 길이 depth:0을 매개변수로 expand() 함수 진입
3. 중심이 되는 섬의 구분자인 2 를 보고, 유효한 범위로 영역을 한 칸씩 확장
3. i) 확장을 하려다, 다른 섬 구분자인 1 을 만나면, 현재 중심이 되는 섬을 기준으로 가장 짧은 다리가 생성되므로, ANSWER를 갱신해주고 함수를 return
3. ii) 확장이 가능하다면, 구분자 2 를 부여하고 다음 방향 계속 탐색
4. 모든 섬 마다 중심이 되는 기준을 탐색.

소스

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

public class Main {
	static int N;
	static boolean[][] VISIT;
	static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 
	static int ANSWER = 100000;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int[][] map = new int[N][N];
		VISIT = new boolean[N][N];
		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());
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(map[i][j] == 1 && !VISIT[i][j]) {
					//땅인데 방문 아직 안한경우 함수 시작
					bfs(i, j, map);
				}
			}
		}			
		System.out.println(ANSWER);
		
	}
	static void bfs(int x, int y, int[][] map) {
		int[][] newMap = new int[N][N];
		//깊은복사
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				newMap[i][j] = map[i][j];
			}
		}
		Queue<Point2146> q = new LinkedList<Point2146>();
		
		q.offer(new Point2146(x, y));
		newMap[x][y] = 2;
		VISIT[x][y] = true;
		
		while(!q.isEmpty()) {
			Point2146 p = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nextX = p.x + dir[i][0];
				int nextY = p.y + dir[i][1];
				
				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
				
				if(newMap[nextX][nextY] == 1) {
					newMap[nextX][nextY] = 2;
					VISIT[nextX][nextY] = true;
					q.offer(new Point2146(nextX, nextY));
				}
			}
		}
		expand(newMap, 0);		
	}
	
	static void expand(int[][] map, int depth) {
		int[][] newMap = new int[N][N];
		//깊은복사
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				newMap[i][j] = map[i][j];
			}
		}
		
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(map[i][j] == 2) {
					for(int k = 0; k < 4; k++) {
						int nextX = i + dir[k][0];
						int nextY = j + dir[k][1];
						
						//지금보고있는 칸은 2로 채워짐
						//다음칸이 범위밖이면 무시
						if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
						
						//다음칸이 1이면 인접하게되니 그때 값을 answer와 비교
						if(map[nextX][nextY] == 1) {
							ANSWER = depth < ANSWER ? depth : ANSWER;
							return;
						}
						//다음칸이 0이면 확장
						else if(map[nextX][nextY] == 0) {
							newMap[nextX][nextY] = 2;
						}
						//다음칸이 2면 아무일 없음
					}
				}
			}
		}
		
		expand(newMap, depth+1);
	}
}

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