[백준] 다리 만들기 2146 - JAVA

문제

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

2146번: 다리 만들기

 

코드

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

public class Main {

	static int n;
	static int board[][];
	static int dx [] = {-1, 0, 1, 0};
	static int dy [] = {0, 1, 0, -1};
	static 	int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		board = new int [n][n];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs();
		findBridge();
		
		System.out.print(min);
		
		
	}
	
	static void bfs() {
		Queue<int []> que = new LinkedList<>();
		boolean visited [][] = new boolean [n][n];

		int idx = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(visited[i][j] || board[i][j] == 0) continue;
				idx += 1;
				que.add(new int[] {i, j});
				visited[i][j] = true;
				
				while(!que.isEmpty()) {
					int [] cur = que.poll();
					board[cur[0]][cur[1]] = idx;
					
					for(int k=0;k<4;k++) {
						int nx = cur[0] + dx[k];
						int ny = cur[1] + dy[k];
						
						if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
						if(visited[nx][ny] || board[nx][ny] == 0) continue;
						
						que.add(new int [] {nx, ny});
						visited[nx][ny] = true;
						
					}
				}
				
			}
		}		
	}
	
	static void findBridge() {

		Queue<int[]> que = new LinkedList<>();
		int dist [][] = new int [n][n];
		
		for(int i=0;i<n;i++) {
			Arrays.fill(dist[i], -1);
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(board[i][j] != 0) {
					dist[i][j] = 0;
					que.add(new int [] {i, j});
				}
			}
		}
		
		while(!que.isEmpty()) {
			int cur [] = que.poll();
			
			for(int k=0;k<4;k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				
				if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
				if(board[nx][ny] == board[cur[0]][cur[1]]) continue;
				
				if(board[nx][ny] == 0) {
					que.add(new int [] {nx, ny});
					dist[nx][ny] = dist[cur[0]][cur[1]] + 1;
					board[nx][ny] = board[cur[0]][cur[1]];
				}
				else {
					min = Math.min(min, dist[nx][ny]+dist[cur[0]][cur[1]]);
				}
			}
		}
	}

}