백준_다리만들기_2146

알고리즘

섬과 섬을 연결할 수 있는 다리의 길이가 최소인값을 찾는 알고리즘

1. dfs탐색을 통해 섬의 정보를 알아야 함. 각각 넘버링

예) 섬이 3개라면 -> 1번섬, 2번섬, 3번섬 

 

2. 섬의 가장자리 즉, 바다와(0) 근접해있는 곳은 bfs탐색을 시작함

- 탐색 기준은 자신의 넘버와 같지않은곳을 따라가면서 탐색(count + 1)

- 해당지점의 넘버링값을 보고 자신의 넘버링값과 다르다면 최소값을 갱신하고 리턴. 단, 현재의 cnt값에서 -1해줘야 함.

- 모든섬이 연결되어 bfs를 돌릴 수 없는 경우도 있을 수 있기 때문에 Ans가 Max값이라면 0 출력! 아니면 Ans값 출력

 

* bfs를 사용한 이유 : 최소값을 찾는 알고리즘이기 때문

 

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

public class 다리만들기_2146 {
	static int N, map[][], Ans = Integer.MAX_VALUE;
	static boolean[][] v;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static Queue<Point> q = new LinkedList<Point>();

	static class Point {
		int r, c, cnt, num;

		public Point(int r, int c, int cnt, int number) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.num = number;
		}

		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}

		@Override
		public String toString() {// 디버깅을 위해
			return "Point [r=" + r + ", c=" + c + ", cnt=" + cnt + "]";
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		v = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		
		int cnt = 1;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if (map[i][j] == 1 && !v[i][j]) {
					dfs(new Point(i, j, cnt));
					cnt++;
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] == 0) continue;
				for (int k = 0; k < 4; k++) {
					int nr = i + dr[k];
					int nc = j + dc[k];

					if (nr < 0 || nc < 0 || nr >= N || nc >= N)
						continue;
					if (map[nr][nc] == 0) {
						bfs(new Point(i, j, 0, map[i][j]), new boolean[N][N]);
						q.clear();
						break;
					}
				}
			}
		}

//		bfs(new Point(0, 2, 0, map[0][2]), new boolean[N][N]);
		System.out.println(Ans == Integer.MAX_VALUE ? 0 : Ans);

//		print(map);

	}

	private static void bfs(Point point, boolean[][] v) {
		v[point.r][point.c] = true;
		q.add(point);

		while (!q.isEmpty()) {

			Point p = q.poll();

			if (map[p.r][p.c] != p.num && map[p.r][p.c] != 0) {
				Ans = Math.min(Ans, p.cnt - 1);
				return;
			}

			for (int k = 0; k < 4; k++) {
				int nr = p.r + dr[k];
				int nc = p.c + dc[k];

				if (nr < 0 || nc < 0 || nr >= N || nc >= N || map[nr][nc] == p.num)
					continue;
				if (!v[nr][nc]) {
					v[nr][nc] = true;
					q.add(new Point(nr, nc, p.cnt + 1, p.num));
				}
			}
		}
	}

	private static void dfs(Point point) {
		Point p = point;
		v[p.r][p.c] = true;
		map[p.r][p.c] = p.cnt;

		for (int k = 0; k < 4; k++) {
			int nr = p.r + dr[k];
			int nc = p.c + dc[k];

			if (nr < 0 || nc < 0 || nr >= N || nc >= N)
				continue;
			if (map[nr][nc] == 1 && !v[nr][nc])
				dfs(new Point(nr, nc, p.cnt));
		}

	}

	private static void print(int[][] map) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

}