Node.js)백준 2146번: 다리 만들기

 

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

2146번: 다리 만들기

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
const dx = [0, 0, -1, 1];
const dy = [1, -1, 0, 0];
const N = +input.shift();
let board = input.map((v) => v.split(' ').map(Number));

let index = 0;

for (let i = 0; i < N; i++) {
	for (let j = 0; j < N; j++) {
		if (board[i][j] == 1) {
			index--;
			board[i][j] = index;
			const q = new Queue();
			q.push([i, j]);
			while (q.length > 0) {
				const [x, y] = q.pop();

				for (let k = 0; k < 4; k++) {
					const nx = x + dx[k];
					const ny = y + dy[k];
					if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] == 0) continue;

					if (board[nx][ny] == 1) {
						board[nx][ny] = index;
						q.push([nx, ny]);
					}
				}
			}
		}
	}
}

let bridge = Array.from(Array(N), () => Array(N).fill(Infinity));
let answer = Infinity;

for (let i = 0; i < N; i++) {
	for (let j = 0; j < N; j++) {
		// console.log(bridge.map((v) => v.join(' ')).join('\n'));
		// console.log('--------------------------------------');
		if (board[i][j] < 0) {
			const start = board[i][j];
			for (let k = 0; k < 4; k++) {
				const ni = i + dx[k];
				const nj = j + dy[k];
				if (ni < 0 || ni >= N || nj >= N || nj < 0) continue;
				if (board[ni][nj] == 0 && bridge[ni][nj] > 1) {
					bridge[ni][nj] = 1;

					const q = new Queue();
					q.push([ni, nj, 1]);

					while (q.length > 0) {
						const [x, y, b] = q.pop();
						for (let l = 0; l < 4; l++) {
							const nx = x + dx[l];
							const ny = y + dy[l];
							if (
								nx < 0 ||
								nx >= N ||
								ny < 0 ||
								ny >= N ||
								board[nx][ny] == start
							) {
								continue;
							}

							if (board[nx][ny] == 0) {
								if (bridge[nx][ny] > b + 1) {
									bridge[nx][ny] = b + 1;
									q.push([nx, ny, b + 1]);
								}
							} else {
								if (board[nx][ny] != start) {
									answer = Math.min(answer, b);
								}
							}
						}
					}
				}
			}
		}
	}
}

console.log(answer);