백준 2146 - 다리 만들기

[문제 바로가기]

 

1. 유형

BFS

 

2. 문제 접근

2-1. 설계

2-2. 해설

BFS를 사용해서 섬을 구합니다.

섬의 개수를 구하는 문제는 아래와 같습니다.

[문제 바로가기 - 백준, 섬의 개수 - 4963]

 

섬의 개수를 구했으면, 섬에서 다른 섬까지의 최단거릴 구하기 위해 다시 BFS를 돌립니다.

그림1

bfs를 돌릴 때, 그림 1처럼 조건을 정해줘야 합니다.

맵을 이탈할 경우 예외처리, 그리고 다름 섬을 만났으면 그 자리에서 거리를 리턴해주면 됩니다.

 

3. 코드

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

public class boj_2146_다리만들기 {
	static int map[][], N, d[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, G[][];
	static boolean check[][];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		map = new int[N][N];
		G = new int[N][N];
		check = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		int idx = 1;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j <  map.length; j++) {
				if (!check[i][j] && map[i][j]==1) {
					check[i][j] = true;
					findGroup(i, j, idx);
					idx++;
				}
			}
		}
		int minval=200;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if(G[i][j]!=0) {
					minval = Math.min(minval, bfs(i,j));
				}
			}
		}
		System.out.println(minval);
	}

	static int bfs(int r, int c) {
		Queue<int[]> q = new LinkedList<>();
		boolean visit[][] = new boolean[N][N];
		q.add(new int[] { r, c, 0 });
		while (!q.isEmpty()) {
			int cur[] = q.poll();
			for (int k = 0; k < 4; k++) {
				int nr = cur[0]+d[k][0];
				int nc = cur[1]+d[k][1];
				if (nr < 0 || nr >= N || nc < 0 || nc >= N || visit[nr][nc])
					continue;
				if(G[nr][nc]!=G[r][c] && G[nr][nc]!=0) {
					return cur[2];
				}
				if(map[nr][nc]==1)
					continue;
				visit[nr][nc] = true;
				q.add(new int[] { nr, nc, cur[2] + 1 });
			}
		}
		return 100;
	}

	static void findGroup(int r, int c, int g) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { r, c });
		G[r][c] = g;
		check[r][c]=true;
		while (!q.isEmpty()) {
			int cur[] = q.poll();
			for (int k = 0; k < 4; k++) {
				int nr = cur[0]+d[k][0];
				int nc = cur[1]+d[k][1];
				if (nr < 0 || nr >= N || nc < 0 || nc >= N || check[nr][nc] || map[nr][nc] == 0)
					continue;
				check[nr][nc] = true;
				G[nr][nc] = g;
				q.add(new int[] { nr, nc });
			}
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}