단지 번호 붙이기

문제

언어

  • JavaScript

문제 풀이 step 1

  • 이번 문제에서는 연결 요소의 개수를 구하고, 각 연결 요소의 크기를 오름차순으로 정렬 후 출력하는 문제입니다.
  • 이번 문제에서는 굳이 주어진 입력을 그래프 형식으로 만들 필요가 없습니다.
    • 한 노드에 도달 시 상하좌우로 갈 수 있는지만 파악하면 됩니다.
  • 우선 BFS 탐색을 이용해서 연결 요소의 개수를 구합니다.
    • 동시에 탐색하는 집 마다 각각의 단지들을 구별할 수 있는 값으로 마킹을 합니다.
    • 이러한 마킹을 이용하면 추가로 방문 처리 배열을 만들 필요가 없습니다. 마킹 자체가 방문처리가 됩니다.
  • 위와 같은 과정을 진행하면 단지의 개수를 구할 수 있고, 각각의 단지들이 다른 값들로 구분됩니다.
    • 마지막으로 구분된 단지들의 크기를 구하고, 오름차순 정렬을 해주면 됩니다.

실수한 점

  • BFS 탐색시에는 DFS 탐색과는 다르게 탐색 전에 방문 처리를 해줘야 하는데 그 부분을 생략하는 바람에 오류를 찾느라 많은 시간을 사용했습니다.
  • 탐색의 시작점에 대한 방문처리를 까먹으면 안 됩니다!
  • arr[i][j] = mark; const queue = [new Dot(i, j)];

소스 코드 1

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

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

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

	// 탐색 시작점 방문처리
	arr[i][j] = mark;
	const queue = [new Dot(i, j)];
	while (queue.length) {
		const from = queue.shift();

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

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

const countHomes = (n, arr, cnt) => {
	const res = Array.from({length: cnt}, () => 0);

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (arr[i][j] === 0) continue;

			res[arr[i][j] - 2] += 1;
		}
	}

	return res;
};

const solution = (input) => {
	const n = Number(input[0]);
	const arr = [];
	for (let i = 1; i < n + 1; i++) {
		arr[i - 1] = input[i].split("").map(Number);
	}

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

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

	const res = countHomes(n, arr, cnt);

	return cnt + "\n" + res.sort((a, b) => a - b).join("\n");
};

console.log(solution(input));