Node.js)백준 17500번: 국경

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

 

class Item {
	next = null;
	constructor(value) {
		this.value = value;
	}
}

class Queue {
	head = null;
	tail = null;
	size = 0;
	constructor() {}

	push(value) {
		const node = new Item(value);
		if (this.head == null) {
			this.head = node;
		} else if (this.tail) {
			this.tail.next = node;
		}
		this.tail = node;
		this.size += 1;
	}

	pop() {
		if (this.head) {
			const popItem = this.head;
			this.head = this.head.next;
			this.size -= 1;
			return popItem.value;
		} else {
			return null;
		}
	}
}

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

const N = +input.shift();
const dir = [
	[-1, 0], // 상
	[1, 0], //  하
	[0, 1], //  우
	[0, -1], //  좌
];

// 국경그래프, 방문그래프 초기화
const graph = Array.from(Array(2 * N + 3), () => Array(2 * N + 3).fill(' '));
graph[0] = graph[0].map((v) => '#');
graph[2 * N + 2] = graph[0].map((v) => '#');
const visited = Array.from(Array(2 * N + 3), () => Array(2 * N + 3).fill(false));
visited[0] = visited[0].map((v) => true);
visited[2 * N + 2] = visited[0].map((v) => true);
visited[1][1] = true;

for (let i = 0; i < 2 * N + 3; i++) {
	graph[i][0] = '#';
	visited[i][0] = true;
	graph[i][2 * N + 2] = '#';
	visited[i][2 * N + 2] = true;
}

for (let i = 1; i < N * 2 + 3; i += 2) {
	for (let j = 1; j < N * 2 + 3; j += 2) {
		graph[i][j] = '+';
	}
}

for (let i = 0; i < N; i++) {
	for (let j = 0; j < N; j++) {
		graph[2 * (i + 1)][2 * (j + 1)] = input[i][j];
	}
}

// 방문그래프는 다음번에도 쓸거라 복사
// 이 그래프는 한붓그리기 방문그래프
const globalVisited = visited.map((v) => [...v]);

// 정답 찾았을 때, 문제 조건에 따라 그래프 변환하는 함수
function drawMap() {
	const answerGraph = Array.from(Array(2 * N + 3), () => new Array());
	for (let i = 0; i < 2 * N + 3; i++) {
		if (i == 0 || i == 2 * N + 2) {
			//바다 그리기
			for (let j = 0; j < N * 3 + N + 1 + 2; j++) answerGraph[i].push('#');
		} else {
			for (let j = 0; j < 2 * N + 3; j++) {
				if (
					// 알파벳이랑 . 공백 양 옆에 공백 추가
					(i % 2 == 1 && graph[i][j].charCodeAt(0) == 32) ||
					graph[i][j].charCodeAt(0) == 46 ||
					(graph[i][j].charCodeAt(0) >= 65 && graph[i][j].charCodeAt(0) <= 90)
				) {
					answerGraph[i].push(' ');
					answerGraph[i].push(graph[i][j]);
					answerGraph[i].push(' ');
				} else if (graph[i][j].charCodeAt(0) == 45) {
					// - 를 --- 로
					answerGraph[i].push(graph[i][j]);
					answerGraph[i].push(graph[i][j]);
					answerGraph[i].push(graph[i][j]);
				} else {
					// 나머지는 그대로
					answerGraph[i].push(graph[i][j]);
				}
			}
		}
	}
	console.log(answerGraph.map((v) => v.join('')).join('\n'));
}

// 국경선에 정해진 영역에 따라 한 종만 포함하는지  확인하는 함수
function check() {
	const vist = visited.map((v) => [...v]);

	for (let i = 2; i < 2 * N + 2; i += 2) {
		for (let j = 2; j < 2 * N + 2; j += 2) {
			if (i <= 1 || j <= 1 || i >= 2 * N + 1 || j >= 2 * N + 1) continue;
			// 영역 밖이면 continue
			if (vist[i][j]) continue;
			// 방문했으면 continue
			if (graph[i][j] == '.') continue;
			// . 이면 continue
			const only = graph[i][j];
			// 이거 말고 다른 알파벳이면 잘못된 국경선
			const q = new Queue();
			q.push([i, j]);
			vist[i][j] = true;
			while (q.size > 0) {
				const [x, y] = q.pop();
				for (let k = 0; k < 4; k++) {
					const nx = x + dir[k][0];
					const ny = y + dir[k][1];
					if (vist[nx][ny]) continue;
					// 이미 방문했으면 continue
					if (
						graph[nx][ny] == '#' ||
						graph[nx][ny] == '-' ||
						graph[nx][ny] == '|' ||
						graph[nx][ny] == '+'
					) {
						// 못가는 곳이면 continue;
						vist[nx][ny] = true;
						continue;
					} else if (
						graph[nx][ny] == ' ' ||
						graph[nx][ny] == '.' ||
						graph[nx][ny] == only
					) {
						// 갈 수 있으면 continue;
						vist[nx][ny] = true;
						q.push([nx, ny]);
					} else {
						// 다른 알파벳이면 잘못된 국경선
						return false;
					}
				}
			}
		}
	}
	return true;
}

// + 돌아다니면서 국경선 그리기 그래프
function drawLine(x, y) {
	if (x == 2 * N + 1 && y == 2 * N + 1 && check()) {
		console.log('yes');
		drawMap();
		process.exit();
	}
	for (let i = 0; i < 4; i++) {
		const nx = x + 2 * dir[i][0];
		const ny = y + 2 * dir[i][1];
		if (nx <= 0 || ny <= 0 || nx >= 2 * N + 2 || ny >= 2 * N + 2) continue;
		if (globalVisited[nx][ny]) continue;
		globalVisited[nx][ny] = true;
		graph[x + dir[i][0]][y + dir[i][1]] = i < 2 ? '|' : '-';
		drawLine(nx, ny);
		globalVisited[nx][ny] = false;
		graph[x + dir[i][0]][y + dir[i][1]] = ' ';
	}
}
drawLine(1, 1);
console.log('no');