그림

문제

언어

  • JavaScript

순서도

  1. BFS 탐색

문제 풀이 step 1

  • 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하는 문제입니다.
  • 단, 그림이라는 것은 1 로 연결된 것을 한 그림이라고 정의합니다.
  • 가로나 세로로 연결된 것은 연결된 것이고, 대각선으로 연결된 것은 떨어진 것입니다.
  • 그림의 넓이란 그림에 포함된 1 의 개수입니다.

문제 풀이 step 2

  • 도화지의 [0, 0] 부터 [n - 1, m - 1] 까지 순회하며, BFS 탐색을 통해서 그림의 개수를 구합니다.
  • 그리고 매 탐색마다 방문한 노드의 개수를 세서 각 그림의 넓이를 구하고, 그 중에서 최대값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

// Queue 구현
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;
	}
}

// 가로, 세로 총 4 가지 방향 정의
const dir = [
	[-1, 0],
	[0, 1],
	[1, 0],
	[0, -1],
];

// 도화지를 넘어가는 경로인지 검사하는 함수
const isPossibleRoute = (n, m, x, y) => 0 <= x && x < n && 0 <= y && y < m;

// BFS 탐색 함수 구현
const bfs = (n, m, paper, visited, x, y) => {
	const queue = new Queue();

	let area = 1;
	visited[x][y] = true;
	queue.enqueue([x, y]);

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

		// 4 가지 방향으로 검사
		for (let i = 0; i < 4; i++) {
			const [tx, ty] = [fx + dir[i][0], fy + dir[i][1]];

			if (!isPossibleRoute(n, m, tx, ty)) continue;
			if (paper[tx][ty] === 0) continue;
			if (visited[tx][ty]) continue;

			// 방문하는 노드마다 넓이 증가
			area += 1;
			visited[tx][ty] = true;
			queue.enqueue([tx, ty]);
		}
	}

	// 최종 넓이 반환
	return area;
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const paper = input.slice(1).map((v) => v.split(" ").map(Number));
	const visited = Array.from({length: n}, () => Array(m).fill(false));

	let max = 0;
	let cnt = 0;
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (paper[i][j] === 0) continue;
			if (visited[i][j]) continue;

			const area = bfs(n, m, paper, visited, i, j);

			// 넓이의 최대값 갱신
			max = Math.max(max, area);
			// 그림의 개수 갱신
			cnt += 1;
		}
	}

	return `${cnt}\n${max}`;
};

console.log(solution(input));