[백준 / JAVA] 2146. 다리 만들기

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

2146번: 다리 만들기

 

---

💻 풀이 결과

💯 최종 코드

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

class Node {
	int r, c;

	Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[][] map = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		Queue<Node> queue = new LinkedList<>();
		boolean[][] visited = new boolean[N][N];
		int[] dr = { 0, 0, -1, 1 };
		int[] dc = { -1, 1, 0, 0 };

		// 섬을 구분하기 위한 작업 -> 섬에 아이디를 부여하는 라벨링 작업
		int idx = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j] && map[i][j] == 1) {
					idx++;
					queue.add(new Node(i, j));
					visited[i][j] = true;
					map[i][j] = idx;

					while (!queue.isEmpty()) {
						Node curr = queue.poll();

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

							// 기저 조건
							if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
								continue;
							}
							if (visited[nr][nc]) {
								continue;
							}

							if (map[nr][nc] == 1) {
								queue.add(new Node(nr, nc));
								visited[nr][nc] = true;
								map[nr][nc] = idx;
							}
						}
					}
				}
			}
		}

//		for (int i = 0; i < N; i++) {
//			System.out.println(Arrays.toString(map[i]));
//		}

		Queue<Node> bridge = new LinkedList<>();
		boolean[][] visitedBridge;	// 메모리 초과 날까봐 다리 방문 처리 배열
		int res = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 시작점
				if (map[i][j] > 0) {
					int cnt = -1; // 다리길이 시작
					visitedBridge = new boolean[N][N];
					queue.add(new Node(i, j));
					visitedBridge[i][j] = true;

					while (!queue.isEmpty()) {
						int size = queue.size();
						cnt++;

						for (int s = 0; s < size; s++) {
							Node curr = queue.poll();

							// 종료 조건 : 다리 완성!
							// 큐 뽑았는데 라벨링 아이디가 나보다 큰 다른 섬이다.
							if (map[curr.r][curr.c] > map[i][j]) {
								res = Math.min(res, cnt - 1);
								queue.clear();
								break;
							}

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

								// 기저 조건
								if (nr < 0 || nc < 0 || nr >= N || nc >= N) { // 경계 밖일 때
									continue;
								}
								if (visitedBridge[nr][nc]) {
									continue;
								}
								
								// 바다 or 라벨링 아이디가 자기보다 큰 다른 섬
								if (map[nr][nc] == 0 || map[nr][nc] > map[i][j]) {
									queue.add(new Node(nr, nc));
									visitedBridge[nr][nc] = true;
								}
							}
						}
					} // while문 끝
				}
			}
		}

		System.out.println(res);
	}
}

💬 풀이 과정

• BFS를 돌면서 섬들을 구분하고 각 섬들에 번호를 부여하는 라벨링 작업까지 구현했다.
• 이후에 아이디어가 생각나지 않아서, 구글링을 통해 여러 아이디어를 참고하는 과정을 거쳤다.
• 번호가 작은 섬부터 다리를 만드는 작업을 한다. 번호 순으로 차례대로 BFS를 돌린다.
• 큐에서 뽑은 현재 노드의 섬 번호를 확인하고, 다리가 출발한 섬의 번호보다 클 때만 BFS를 종료한다.
• 다리가 출발한 섬의 번호랑 같거나 번호보다 작다면 이미 자기 자신으로 이어지거나 이미 최소 다리 길이를 구한 섬의 관계이기 때문에 넘겨야한다.
• 방문하지 않았고, 바다이거나 라벨링 아이디가 현재 섬보다 큰 땅이면 큐에 삽입한다.
• BFS를 돌면서 0(바다)을 탐색하다가 섬의 번호가 다른 땅에 도착하면 그것이 다리의 최소 길이라고 생각하는 것이 중요하다.

💡 깨달은 점

1. 섬을 라벨링 하는 작업

• 각각 다른 섬이라는 것을 인지하기 위해서 섬들을 라벨링하며 아이디나 번호를 부여한다.

2. 여러 아이디어, 그리고 생각한 풀이대로 일단 구현해 보기

• 여러 아이디어를 참고해서 나에게 가장 맞는 풀이 방법을 찾는 것이 중요하다.
• 일단 생각해 본 아이디어대로 구현을 시도해보는 것도 중요하다.