섬의 개수

문제

언어

  • JavaScript

문제 풀이 step 1

  • 이번 문제는 연결 요소의 개수를 구하는 문제입니다.
  • 백준 2667번 - 단지 번호의 개수 풀이 와 유사한 문제입니다.
  • 단, 이번 문제에서는 상하좌우에 추가로 대각선 4 방향까지 고려해야 합니다.
  • 그 부분만 추가하면 큰 차이는 없습니다.

소스 코드 1

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

const VISITED_MARK = 2;

class Dot {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
}

const BFS = (w, h, i, j, arr) => {
	const cx = [0, 0, 1, -1, 1, 1, -1, -1];
	const cy = [1, -1, 0, 0, -1, 1, -1, 1];

	arr[i][j] = VISITED_MARK;
	const queue = [new Dot(i, j)];
	while (queue.length) {
		const from = queue.shift();

		for (let i = 0; i < 8; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);

			if (
				0 <= to.x &&
				to.x < h &&
				0 <= to.y &&
				to.y < w &&
				arr[to.x][to.y] === 1
			) {
				arr[to.x][to.y] = VISITED_MARK;
				queue.push(to);
			}
		}
	}
};

const solution = (input) => {
	let res = "";
	let index = 0;

	while (true) {
		const [w, h] = input[index++].split(" ").map(Number);
		if (w === 0 && h === 0) break;

		const arr = [];
		for (let i = index; i < index + h; i++) {
			arr.push(input[i].split(" ").map(Number));
		}
		index += h;

		let cnt = 0;
		for (let i = 0; i < h; i++) {
			for (let j = 0; j < w; j++) {
				if (arr[i][j] !== 1) continue;

				cnt += 1;
				BFS(w, h, i, j, arr);
			}
		}

		res += `${cnt}\n`;
	}

	return res;
};

console.log(solution(input));