[백준 2146번] 다리 만들기 (java)

사용한 방법 : DFS, BFS

 

풀이 

1. 반복문을 통해 2차원 배열 map에서 1(대륙)인 위치(n,m)를 찾는다.

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		if (map[i][j] == 1) {
			isvisited = new boolean[N][N];
			sameLand(i, j);  // 같은 섬에 속하는 위치들의 isvisited를 true로 변경
			bfs(i, j);
		}
	}
}

2. 해당 지점을 포함하는 섬을 dfs방법으로 탐색한 후에 해당 위치들을 isvisited[i][j]=true로 변경한다.

   여기서 isvisited[i][j]=true이며 map[i][j]=1인 위치는 (n,m)위치의 대륙과 동일한 섬에 속함을 의미한다.

public static void sameLand(int sn, int sm) {

	isvisited[sn][sm] = true;

	for (int i = 0; i < 4; i++) {
		int n = sn + y[i];
		int m = sm + x[i];

		if ((0 <= n && n < N) && (0 <= m && m < N)) {
			if (map[n][m] == 1 && !isvisited[n][m])
				sameLand(n, m);
		}
	}
}

3. 1번에서의 위치(n,m)에서부터 bfs방법을 통해 또 다른 1(대륙) 위치를 찾으면 그 동안 지나온 0의 개수(다리 길이)와

   기존의 다리 길이 최솟값(res)을 비교하여 더 작은 값을 res에 넣는다. -> res=Math.min(res,p,count);

   (단, 찾은 1이 isvisited[i][j]=false이어야 한다. isvisited[i][j]=true이면

   1번에서의 위치와 같은 섬에 속함을 의미하기 때문에, 같은 섬 내에서 다리를 놓는 경우가 되버린다.)

public static void bfs(int sn, int sm) {
		Queue<Pair> q = new LinkedList<>();

		q.add(new Pair(sn, sm, 0));

		while (!q.isEmpty()) {
			Pair p = q.poll();

			for (int i = 0; i < 4; i++) {
				int n = p.n + y[i];
				int m = p.m + x[i];

				if ((0 <= n && n < N) && (0 <= m && m < N)) {

					if (map[n][m] == 0 && !isvisited[n][m]) {
						isvisited[n][m] = true;
						q.add(new Pair(n, m, p.count + 1));
				}
				else if (map[n][m] == 1 && p.count > 0 && !isvisited[n][m])
					res = Math.min(res, p.count);
			}
		}
	}
}

 

 

 

전체코드

package num2146;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static int[][] map;
	static boolean[][] isvisited;
	static int N;
	static int res = Integer.MAX_VALUE;
	static int[] x = { 0, 1, 0, -1 };
	static int[] y = { 1, 0, -1, 0 };

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		for (int i = 0; i < N; i++) {
			String[] arr = br.readLine().split(" ");
			for (int j = 0; j < N; j++)
				map[i][j] = Integer.parseInt(arr[j]);
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1) {
					isvisited = new boolean[N][N];
					sameLand(i, j);  // 같은 섬에 속하는 위치들의 isvisited를 true로 변경
					bfs(i, j);
				}
			}
		}
		if (res == Integer.MAX_VALUE)
			res = 0;

		bw.write(res + "\n");
		bw.flush();
	}

	public static void bfs(int sn, int sm) {
		Queue<Pair> q = new LinkedList<>();

		q.add(new Pair(sn, sm, 0));

		while (!q.isEmpty()) {
			Pair p = q.poll();

			for (int i = 0; i < 4; i++) {
				int n = p.n + y[i];
				int m = p.m + x[i];

				if ((0 <= n && n < N) && (0 <= m && m < N)) {

					if (map[n][m] == 0 && !isvisited[n][m]) {
						isvisited[n][m] = true;
						q.add(new Pair(n, m, p.count + 1));
					}

					else if (map[n][m] == 1 && p.count > 0 && !isvisited[n][m])
						res = Math.min(res, p.count);
				}
			}
		}
	}

	public static void sameLand(int sn, int sm) {

		isvisited[sn][sm] = true;

		for (int i = 0; i < 4; i++) {
			int n = sn + y[i];
			int m = sm + x[i];

			if ((0 <= n && n < N) && (0 <= m && m < N)) {
				if (map[n][m] == 1 && !isvisited[n][m])
					sameLand(n, m);
			}
		}
	}
}

class Pair {
	int n, m, count;

	Pair(int n, int m, int count) {
		this.n = n;
		this.m = m;
		this.count = count;
	}
}