다리 만들기

문제

백준 2146번 - 다리 만들기

언어

JavaScript

순서도

graph 생성
각각의 육지들을 구분하기 위한 그룹화
그룹화된 각각의 육지들에서 BFS 탐색

문제 풀이 step 1

graph 생성
- 우선 주어진 입력에 맞춰서 2 차원 배열인 graph 를 생성합니다.
육지 구분
- 이후에 각각의 육지들이 BFS 방식으로 자신의 테두리에서 1 크기 씩 다리를 놓는 방식으로 구현합니다.
- 이렇게 각각의 육지들이 크기가 커지다 보면 서로 마주 닿게 되는 상황이 옵니다.
- 그 때 육지가 구분이 되어 있어야, 마주 닿은 부분인 다리인지 판별을 할 수 있기 때문에 이 과정이 필요한 것입니다.
- 그래프적으로 말을 바꿔서 설명을 하면, 연결 요소를 구분하는 것이라고 볼 수 있겠습니다.
- 이 부분은 group 이라는 2 차원 배열을 생성하고, BFS 탐색을 하면서 같은 육지끼리 같은 값을 가지게 함으로써 구현할 수 있습니다.
그룹화된 각각의 육지들에서 BFS 탐색
- 이전 육지를 구분하는 단계에서 queue 에 육지인 노드들을 미리 넣어놓고, 이 노드들을 가지고 BFS 탐색을 실시합니다.
- 각각의 육지에서 바다 쪽으로 1 크기의 다리를 놓는 방식으로 BFS 탐색을 실시합니다.
- 바다 쪽으로 1 크기의 다리를 놓을 때, 주변에 바다라면 다리를 놓고, 주변에 다른 육지의 다리가 있다면 다리 크기를 계산합니다.
- 다리 크기를 계산할 때마다 최솟값을 갱신합니다.

모든 과정을 수행하고, 계산해낸 최솟값이 정답이 됩니다.

후기

꼭 다시 풀어볼 문제입니다. 각각 육지에서 동시에 자신의 몸집을 키우는 방식이 상당히 흥미롭습니다.
각각의 육지들을 구분하는 함수를 DFS 로 구현했는데 스택 오버 플로우가 발생해서 BFS 로 구현했습니다.
Java 로 구현한 풀이는 그런 문제가 없었는데 JavaScript 로 구현하니 이런 문제가 발생해서 조금 놀랐습니다. 아니면 제가 잘못 구현한 것일 수도 있습니다.
이 뿐만 아니라 다른 곳에서도 문제가 발생했을 수도 있을 것 같아서 최대한 호출이나 반복을 줄이는 방식으로 구현했습니다.
그래서 육지를 구분하는 과정 속에서 동시에 다음 BFS 탐색을 위해서 Queue 에 육지인 노드를 넣어주는 과정을 포함시켰습니다.
하지만 이렇게 하고 보니, 한 육지가 커지고, 그 다음 육지가 커지고 또 그 다음 육지가 커지는 이런 방식으로 진행이 되니까 오히려 흐름이 더 자연스러운 것 같습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

class Dot {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
}

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	isEmpty() {
		return this.front === this.rear;
	}

	enqueue(data) {
		this.bucket[++this.front] = data;
	}

	dequeue() {
		if (!this.isEmpty()) return this.bucket[++this.rear];
	}
}

const cx = [0, 0, 1, -1];
const cy = [1, -1, 0, 0];

// 방문하려는 노드가 2 차원 배열을 안에 있는지 판별하는 함수
const isPossibleRoute = (n, to) =>
	0 <= to.x && to.x < n && 0 <= to.y && to.y < n;

// 각각의 육지들을 구분하기 위해서 그룹화
const markGroupByBFS = (n, graph, group, typeNum, start, routeQueue) => {
	const groupQueue = new Queue();

	group[start.x][start.y] = typeNum;
	groupQueue.enqueue(start);
	routeQueue.enqueue(start);

	while (!groupQueue.isEmpty()) {
		const from = groupQueue.dequeue();

		for (let i = 0; i < 4; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);
			if (
				!isPossibleRoute(n, to) ||
				graph[to.x][to.y] === 0 ||
				group[to.x][to.y] !== 0
			)
				continue;

			group[to.x][to.y] = typeNum;
			groupQueue.enqueue(to);
			// 동시에 다음 BFS 를 위해서 queue 에 육지인 노드 담기
			routeQueue.enqueue(to);
		}
	}
};

// 각각의 육지에서 다리를 놓으며 탐색을 하다가 다른 육지의 다리를 만나면 가장 작은 다리 길이를 계산하는 함수
const getMinRouteByBFS = (n, graph, group, routeQueue) => {
	let distance = 10000;

	while (!routeQueue.isEmpty()) {
		const from = routeQueue.dequeue();

		for (let i = 0; i < 4; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);
			if (!isPossibleRoute(n, to)) continue;

			if (graph[to.x][to.y] === 0) {
				group[to.x][to.y] = group[from.x][from.y];
				graph[to.x][to.y] = graph[from.x][from.y] + 1;
				routeQueue.enqueue(to);
			} else {
				if (group[to.x][to.y] === group[from.x][from.y]) continue;

				// 바다가 아니고 다른 육지의 다리라면 거리 갱신
				distance = Math.min(
					distance,
					graph[to.x][to.y] + graph[from.x][from.y] - 2
				);
			}
		}
	}

	return distance;
};

const solution = (input) => {
	const n = parseInt(input[0]);

	// 1. graph 생성
	const graph = [];
	for (let i = 1; i < n + 1; i++) {
		graph[i - 1] = input[i].split(" ").map(Number);
	}

	// 2. 육지 구분과 동시에 routeQueue 에 넣기
	let typeNum = 1;
	const routeQueue = new Queue();
	const group = Array.from({length: n}, () => Array.from({length: n}, () => 0));
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			// 바다 or 이미 그룹 지정이 되었으면
			if (graph[i][j] === 0 || group[i][j] !== 0) continue;

			const start = new Dot(i, j);
			markGroupByBFS(n, graph, group, typeNum, start, routeQueue);
			typeNum += 1;
		}
	}

	// 3. 모든 육지에서 BFS 탐색 하며 최단 거리의 다리 찾기
	const distance = getMinRouteByBFS(n, graph, group, routeQueue);

	return distance;
};

console.log(solution(input));