양

문제

언어

  • JavaScript

순서도

  1. 영역 하나마다 BFS 탐색을 하며 양과 늑대가 몇 마리인지 세기
  2. 양이 많으면 늑대를 제거하고, 늑대가 양과 같거나 더 많으면 양을 제거
  3. 최종적으로 양과 늑대가 몇 마리인지 출력

문제 풀이 step 1

  • 마당에 특정 수의 양과 늑대가 있습니다.
  • 마당은 행과 열로 이루어진 직사각형 모양입니다.
    • ”.” 은 빈 필드
    • ”#” 은 울타리
    • “o” 는 양
    • “v” 는 늑대
  • 마당 안에서 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고, 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 할 수 있습니다.
  • 마당에서 “탈출”할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주합니다.
  • 다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아냅니다.
  • 그렇지 않으면 늑대가 그 영역 안의 모든 양을 먹습니다.
  • 시간이 지나고 나서 살아남은 양과 늑대의 수를 출력하는 문제입니다.

문제 풀이 step 2

  • 우선, 마당의 각 영역에 대해서 BFS 탐색을 진행합니다.
  • 각 영역마다 양과 늑대가 몇 마리인지 세고, 양이 많으면 늑대를 제거하고, 늑대가 양보다 같거나 많으면 양을 제거합니다.
  • 최종적으로 양과 늑대가 몇 마리인지 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

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

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

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

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

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

// 마당을 넘어가는지 검사하는 함수
const isPossibleRoute = (r, c, x, y) => 0 <= x && x < r && 0 <= y && y < c;

const BFS = (r, c, yard, visited, i, j) => {
	let [sheep, wolf] = [0, 0];
	const queue = new Queue();

	// 탐색을 시작한 칸에 양이 있는지 늑대가 있는지 검사
	if (yard[i][j] === "v") wolf += 1;
	if (yard[i][j] === "o") sheep += 1;
	visited[i][j] = true;
	queue.enqueue([i, j]);

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

		for (let i = 0; i < 4; i++) {
			const [tx, ty] = [fx + cx[i], fy + cy[i]];

			// 마당을 벗어났거나 이미 방문한 칸이거나 울타리라면 탐색하지 않음
			if (!isPossibleRoute(r, c, tx, ty)) continue;
			if (visited[tx][ty]) continue;
			if (yard[tx][ty] === "#") continue;

			// 탐색하는 칸에 양이 있는지 늑대가 있는지 검사
			if (yard[tx][ty] === "v") wolf += 1;
			if (yard[tx][ty] === "o") sheep += 1;
			visited[tx][ty] = true;
			queue.enqueue([tx, ty]);
		}
	}

	// 양이 늑대보다 많으면 늑대 제거
	if (sheep > wolf) return [sheep, 0];
	// 늑대가 양보다 같거나 많으면 양 제거
	return [0, wolf];
};

const solution = (input) => {
	const [r, c] = input[0].split(" ").map(Number);
	const yard = input.slice(1).map((v) => v.split(""));

	let [sheepSum, wolfSum] = [0, 0];
	const visited = Array.from({length: r}, () => Array(c).fill(false));
	for (let i = 0; i < r; i++) {
		for (let j = 0; j < c; j++) {
			// 방문한 칸이거나 울타리라면 탐색하지 않음
			if (visited[i][j]) continue;
			if (yard[i][j] === "#") continue;

			// BFS 탐색을 통해서 살아남은 양 또는 살아남은 늑대 구하기
			const [sheep, wolf] = BFS(r, c, yard, visited, i, j);
			sheepSum += sheep;
			wolfSum += wolf;
		}
	}

	return `${sheepSum} ${wolfSum}`;
};

console.log(solution(input));