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

문제도 이해가 가고 푸는 법도 대강 알겠는데 

어떤 문제 떄문에 결국 못풀었던 문제였었는데 ( 자그마치 4달전이라 함..)

오늘 다시 도전했다.

저번에 풀었던 코드와 비교해보니 섬세함이 줄었는데

대신 깔끔함과 가독성이 증가했다. ( 저번 코드에 비해서 )

섬과 섬 사이에서 가장 가까운 다리를 놓는 방식인데

1. 섬과 섬을 구분 하고

.2 거기서 bfs로 가장 가까운 섬과의 거리를 재서 출력하면 된다. 

초기화를 신경 안쓰고 

다른 섬을 찾았을 경우를 구분 해주니 정답으로 인정되었다

예전 풀었던 문제를 보니까..기억이 안난다...

그리고

뭔가 예전의 열정이 가끔 그립다 ㅠㅠ

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

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


public class Main_backjoon_2146_다리만들기 {
	static int N;
	static int[] dx = { 1, -1 ,0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int[][] MAP = new int[101][101];
	static boolean[][] visited = new boolean[101][101];
	static ArrayList islandArr = new ArrayList();
	static Queue q =  new LinkedList();
	static int MIN = 9999;
	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 index = 0;
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine() , " ");
			while(st.hasMoreTokens()) {
				MAP[i][index] = Integer.parseInt(st.nextToken());
				index += 1;
			}
			index = 0;
		}
		
		//printMap();
		int idx = 0 ; 
		for(int i = 0 ; i < N; i ++) {
			for(int j =0 ; j < N ; j++) {
				if( !visited[i][j] && MAP[i][j] != 0  ) {
					idx+= 1;
					namingIsland(i,j, idx);
				}
			}
		}
		//printMap();
		
		for(int i = 0 ; i < islandArr.size(); i++) {
			IslandPoint ip = islandArr.get(i);
			bulidingBridge(ip.y, ip.x, MAP[ip.y][ip.x]);
;		}
		System.out.println(MIN);
		
	}
	public static void bulidingBridge(int y, int x, int idx ) {
		visited = new boolean[101][101];
		q.clear();
		q.add(new IslandPoint(y, x));
		visited[y][x] = true;
		int count = 0;
		boolean findIsland = false;
		
		loop: while(!q.isEmpty()) {
			int qsize = q.size();
			for(int s = 0 ; s < qsize; s++) {
				IslandPoint ip = q.poll();
				for(int i = 0; i< 4; i++) {
					int yy = dy[i] + ip.y;
					int xx = dx[i] + ip.x;
					if(xx >= 0 && xx < N && yy >= 0 && yy < N ) {
						
						if(MAP[yy][xx] == 0 && visited[yy][xx]  == false) {
							q.add(new IslandPoint(yy,xx));
							visited[yy][xx] = true;
						}
						if( MAP[yy][xx] != 0 && MAP[yy][xx] != idx) {
							findIsland = true;
							break loop;
						}
					}
				}	
			}
			count +=1;
		}
		if( findIsland ) {
			if( MIN > count) {
				MIN = count;
			}	
		}
	}
	/* 섬 색깔 칠하기 */ 
	public static void namingIsland(int y, int x , int idx) {
		q.add(new IslandPoint(y, x));
		visited[y][x] = true;
		MAP[y][x] = idx;
		islandArr.add(new IslandPoint(y, x));
		while(!q.isEmpty()) {
			IslandPoint ip = q.poll();
			for(int i = 0; i< 4; i++) {
				int yy = dy[i] + ip.y;
				int xx = dx[i] + ip.x;
				if(xx >= 0 && xx < N && yy >= 0 && yy < N ) {
					if(MAP[yy][xx] == 1 && visited[yy][xx]  == false) {
						MAP[yy][xx] = idx;
						q.add(new IslandPoint(yy,xx));
						visited[yy][xx] = true;
						if( MAP[yy][xx] != 0) {
							islandArr.add(new IslandPoint( yy, xx ));
						}
					}
				}
			}
		}
	}
	public static void printMap() {
		for (int i = 0 ; i< N; i++) {
			for(int j =0 ; j < N ; j++) {
				System.out.print(MAP[i][j] + " ");
			}
			System.out.println();
		}
	}
	public static void printVisited() {
		for (int i = 0 ; i< N; i++) {
			for(int j =0 ; j < N ; j++) {
				if ( MAP[i][j] != 0  && visited[i][j]) {
					System.out.print("9 ");
				}else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}
	}
}