[BOJ/JAVA] 백준 2146번 : 다리 만들기

2146번: 다리 만들기

 

---

 

 

• 생각

 

dfs방식으로 풀면 될 것 같다라고 생각한다.

 

dfs방식

1. 모든 섬의 칸을 queue에 넣는다.

2. bfs를 돌린다. (0을 만나면 시작)

3. 섬을 만나면 return하면서 지나온 0의 칸수와 지금까지 가장 짧았던 0의 칸수로 비교
==> 문제가 되는 것은 bfs를 돌면서 같은 섬으로 갈 수 있다는 것

 

 

 

참고)

백준 2146 / 다리 만들기 / BFS / JAVA / 골드 3

이제 문제를 보도록 하자. N X N의 배열이 주어지고 섬이 있는 곳은 1, 없는 곳은 0으로 input 값이 들어온다. 나는 이 값을 받는 inputArr 행렬을 하나 만들고, 각 섬들을 그룹화한 groupArr, 섬으로부터의 거리를 나타낸 distArr 이렇게 세 개의 배열을 만들어서 문제를 풀었다. groupArr는 섬을 한 그룹씩 순서대로 인덱싱을 해서 1,2,3, .. 이런식으로 같은 섬은 같은 숫자를 입력해 주었다. 그리고 distArr는 섬인 경우는 초기값을 0으로 나머지는(섬이 아닌 곳) -1로 해서 구분을 해 주었다. (그림에서 빈 칸은 모두 초기값 0이며 생략했다)

 

 

이렇게 만들고 나서 distArr에서 BFS를 통해 모든 점에 대해 섬에서부터 거리가 얼마나 되는지를 계산한다. 섬 위에 있다면 당연히 그 값은 0이다. 그리고 그 섬에서 인접한 값들은 1이고 그 값에서 인접한 값은 2일 것이다. 그런식으로 -1로 초기에 설정된 점들은 섬들로부터 최단거리를 계산해서 그 값을 넣어 준다.

 

 

이렇게 거리를 계산하다보면 인접한 점의 distArr 배열값이 이미 자연수로 정해진 경우가 있다. 그 경우는 값을 갱신해 주지 않는다. 즉, distArr에서 모든 점을 탐색하고 나면 각각의 점은 섬으로부터의 최단 거리가 되는 것이다. 그렇게 계산을 마치면, distArr에서 임의의 한 점과 그 인접한 점의 합이 최소가 되는 점을 찾는다. 그 값이 최단거리가 되는 것이다.

 

 

물론 BFS로 계산을 하는 것이니, 거리가 1인 점들을 다 찾고 그 다음 거리가 2인 점을 찾을 것이다. 즉 값을 입력하는 순서가 거리 오름차순이라는 의미이다. 따라서 인접한 두 점이 발견되면 바로 그 순간 두 섬 사이의 거리를 계산해서 리턴해 주어도 된다.

 

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Algorithm {
	static int N, answer, array[][], distanceArray[][], groupArray[][];
	static int[] x = { 0, 0, 1, -1 };
	static int[] y = { 1, -1, 0, 0 };

	public static void main(String[] args) throws Exception {
		SetData();
		bfs();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		array = new int[N][N];
		distanceArray = new int[N][N];
		groupArray = new int[N][N];
		answer = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				array[j][i] = in.nextInt();
			}
		}
	}

	private static void bfs() {
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (array[i][j] != 1 || groupArray[i][j] != 0)
					continue; // array가 1이고 g를 초기화 안했다면

				Queue<int[]> queue = new LinkedList<>();
				groupArray[i][j] = ++count; // g를 초기화
				queue.add(new int[] { i, j });
				while (!queue.isEmpty()) {
					int[] location = queue.remove();

					for (int k = 0; k < 4; k++) {
						int r = location[0] + x[k];
						int c = location[1] + y[k];
						if (r < 0 || r >= N || c < 0 || c >= N)
							continue;

						if (array[r][c] == 1 && groupArray[r][c] == 0) {
							queue.add(new int[] { r, c });
							groupArray[r][c] = count;
						}
					}
				}
			}
		}

		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				distanceArray[i][j] = -1;
				if (array[i][j] == 1) {
					queue.add(new int[] { i, j });
					distanceArray[i][j] = 0;
				}
			}
		}
		while (!queue.isEmpty()) {
			int[] location = queue.remove();

			for (int k = 0; k < 4; k++) {
				int r = location[0] + x[k];
				int c = location[1] + y[k];

				if (r < 0 || r >= N || c < 0 || c >= N)
					continue;

				if (distanceArray[r][c] == -1) {
					distanceArray[r][c] = distanceArray[location[0]][location[1]] + 1;
					groupArray[r][c] = groupArray[location[0]][location[1]];
					queue.add(new int[] { r, c });
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < 4; k++) {
					int r = i + x[k];
					int c = j + y[k];
					if (r < 0 || r >= N || c < 0 || c >= N)
						continue;

					if (groupArray[i][j] != groupArray[r][c])
						answer = Math.min(answer, distanceArray[i][j] + distanceArray[r][c]);

				}
			}
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}