침투

문제

언어

  • JavaScript

순서도

  1. 0 번 행의 모든 흰색 격자를 시작점으로 BFS 탐색 수행
  2. n - 1 번 행의 흰색 격자 중에서 방문 처리가 된 격자가 있는지 검사

문제 풀이 step 1

  • 인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투할 수 있는 섬유 물질을 개발하고 있습니다.
  • 이 섬유 물질은 2 차원 N x M 격자로 표현될 수 있습니다. 편의상 2 차원 격자의 위쪽을 바깥쪽, 아래쪽을 안쪽이라고 생각하기로 합니다.
  • 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻합니다.
  • 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있습니다.
  • 김 교수가 개발한 섬유 물질을 나타내는 정보가 2 차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 문제입니다.

문제 풀이 step 2

  • 본 문제는 BFS 탐색 알고리즘을 적용하면 간단하게 해결할 수 있습니다.
  • 핵심은 바깥쪽에서 흘려보낸 전류가 안쪽까지 침투할 수 있느냐를 판단하는 것입니다.
  • 그래서 격자의 바깥쪽에 있는 모든 흰 칸들을 시작점으로 해서 BFS 탐색을 수행합니다.
  • 탐색 후 격자의 안쪽에 도달한 전류가 있는지 검사하고 있다면 “YES” 없다면 “NO” 를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

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

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

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

// 상, 하, 좌, 우
const dir = [
	[0, -1],
	[0, 1],
	[-1, 0],
	[1, 0],
];

// 격자를 벗어나는지 검사
const isPossibleRoute = (n, m, x, y) => 0 <= x && x < n && 0 <= y && y < m;

const bfs = (n, m, grid, sx, sy) => {
	const queue = new Queue();

	queue.enqueue([sx, sy]);
	grid[sx][sy] = 2;

	while (!queue.isEmpty()) {
		const [fx, fy] = queue.dequeue();

		// 총 4 가지 방향으로 탐색
		for (let i = 0; i < 4; i++) {
			const [nx, ny] = [fx + dir[i][0], fy + dir[i][1]];

			if (!isPossibleRoute(n, m, nx, ny)) continue;
			if (grid[nx][ny] !== 0) continue;

			queue.enqueue([nx, ny]);
			grid[nx][ny] = 2;
		}
	}
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);

	const grid = input.slice(1).map((v) => v.split("").map(Number));

	// 격자의 바깥쪽에서 BFS 탐색을 수행
	for (let i = 0; i < m; i++) {
		if (grid[0][i] !== 0) continue;

		bfs(n, m, grid, 0, i);
	}

	// 격자의 안쪽에 도달한 전류가 있는지 검사 후 적절한 결과를 반환
	for (let i = 0; i < m; i++) {
		if (grid[n - 1][i] === 2) return "YES";
	}

	return "NO";
};

console.log(solution(input));