[2146] 다리 만들기

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

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

class Main {

	static int N, num, bridge;
	static int[][] map, arr;
	static boolean[][] visited;
	static int[][] dir = {{-1,0},{0,-1},{0,1},{1,0}};
	static Queue<Pair> queue;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];
		arr = new int[N][N];
		visited = new boolean[N][N];
		
		num = 1;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j] == 1 && !visited[i][j]) {
					DFS(i, j);
					num++;
				}
			}
		}
		
		int answer = 99999999;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(arr[i][j] != 0) {
					visited = new boolean[N][N];
					copy();
					bridge=0;
					BFS(i, j);
//					System.out.println(bridge);
//					print();
//					System.out.println();
					if(bridge != 1) 
					answer = Math.min(answer, bridge);
				}
			}
		}
		
		System.out.println(answer-1);
	}
	
	public static void BFS(int x, int y) {
		queue = new LinkedList<Pair>();
		queue.offer(new Pair(x, y, map[x][y]));
		visited[x][y] = true;
		
		while(!queue.isEmpty()) {
			
			int len = queue.size();
			
			bridge++;
			
			for(int i=0; i<len; i++) {
				Pair p = queue.poll();
				
				for(int j=0; j<4; j++) {
					int nx = p.x + dir[j][0];
					int ny = p.y + dir[j][1];
					
					if(isInside(nx, ny) && !visited[nx][ny] && (map[nx][ny] == 0 || map[nx][ny] != p.n)) {
						if(map[nx][ny] != p.n && map[nx][ny] != 0) return;
						queue.offer(new Pair(nx, ny, p.n));
						visited[nx][ny] = true;
						map[nx][ny] = p.n;
					}
				}
			}
		}
		
	}

	public static void DFS(int x, int y) {
		visited[x][y] = true;
		arr[x][y] = num;
		
		for(int i=0; i<4; i++) {
			int nx = x+dir[i][0];
			int ny = y+dir[i][1];
			
			if(isInside(nx, ny) && !visited[nx][ny] && arr[nx][ny] == 1) {
				DFS(nx, ny);
			}
		}
	}

	public static boolean isInside(int x, int y) {
		if (x >= 0 && x < N && y >= 0 && y < N)
			return true;
		else
			return false;
	}
	
	public static void copy() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = arr[i][j];
			}
		}
	}
	
	public static void print() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

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

---

2차원 배열에 여러개의 섬이 주어졌을 때, 2개의 섬과 섬사이를 잇는 다리 중에 가장 짧은 다리의 길이를 구하는 문제입니다. 처음에 각 섬은 다 1로 표시되어있기 때문에 각 섬에 DFS를 이용해서 번호를 매겼습니다. 그리고 각 섬에서 BFS 하는데 그 섬의 좌표를 x, y에 섬의 번호를 n에 저장해서 n과 다르거나 0이면 BFS를 했습니다. 그러면 섬의 가장자리에서 BFS가 수행되고, 다른 섬을 만났을 때 BFS가 종료되서 다리의 길이가 나오게 됩니다. 그렇게 다리의 길이를 하나씩 구하면서 최솟값을 구하게 되면 정답입니다.

[ 문제 풀이 ]

1. 좌표를 2차원 배열에 입력받고, 다시 탐색하면서 1일 때 DFS를 해서 각 섬에 번호를 매겨줍니다.

2. 그리고 다시 반복문을 2차원 배열 모두 돌게 되는데, 섬을 만나게 되면 visited를 초기화 시켜주고, copy() 함수를 실행시키는데, copy() 함수는 처음 섬에 번호를 매겼던 배열을 복사하는 함수입니다. 그리고 BFS를 할 때마다 다리 길이를 초기화 시켜줘야하므로 다리 길이를 표현하는 bridge도 초기화 시켜줍니다.

3. 이제 그 좌표에서 BFS를 하는데, 그 좌표를 Queue에 넣을 때 좌표와 그 섬의 번호까지 3개를 넣어줍니다.

3-1. 상하좌우를 확인할 때 좌표가 0이고 현재 섬번호와 다를 때 BFS를 해주는데, 현재 섬 번호와 다르게 되면 다리 길이를 구한것이므로 BFS를 종료하고, 0이면 계속 BFS를 해서 다리 길이를 확장해줍니다.

4. 다리 길이를 각 섬의 끝에서 구했으면 다리길이의 최솟값을 출력해줍니다.