[백준 2667] 단지번호붙이기
February 11, 2023
문제
https://www.acmicpc.net/problem/2667
아이디어
- 2차원 배열을 만들어서, 집이 있는 곳과 집이 없는 곳의 좌표 정보를 정리한다.
-
모든 노드를 대상으로 아래 로직을 수행한다.
- 이미 방문한 노드라면 다음으로 넘어간다.
- 집이 없는 공간이라면 다음으로 넘어간다.
-
집이 있는 공간이라면 큐에 현재 노드의 좌표를 넣고 방문처리 후 큐가 빌 때까지 아래 로직을 수행한다. (BFS 탐색)
- 집의 갯수를 기록하는 카운트 변수를 증가시킨다.
- 현재 노드의 상하좌우 이어져있는 노드 중에서 집이 있으면 해당 좌표를 방문처리후 큐에 넣는다.
- 이어져 있는 집을 전부 찾았다면 해당 카운트 변수를 기록한다.
- 각 단지별 집의 갯수를 기록한 카운트 변수의 배열을 오름차순으로 정렬후 출력한다.
소스코드
// 입력 정제
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const map = [];
const visited = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
for (let i = 1; i <= n; i++) {
map.push(input[i].split("").map(e => Number(e)));
}
// 문제
function isInBoundary(y, x) {
if (y < 0 || y >= n) return false;
if (x < 0 || x >= n) return false;
return true;
}
function solution() {
const town = []; // 각 단지에 붙어있는 집의 갯수
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (visited[i][j]) continue; // 이미 방문한 공간이면 스킵
if (!map[i][j]) continue; // 집이 없는 공간이면 스킵
// 집이 있는 곳이면 이어진 모든 집을 찾아서 BFS 탐색
visited[i][j] = 1;
const queue = [[i, j]];
const direction = [[0, 1], [1, 0], [0, -1], [-1, 0]];
let numOfHouse = 0; // 붙어있는 집의 갯수
while (queue.length > 0) {
const [nowY, nowX] = queue.shift();
numOfHouse++;
direction.forEach(([dy, dx]) => {
const nextY = nowY + dy;
const nextX = nowX + dx;
if (isInBoundary(nextY, nextX) && map[nextY][nextX] && !visited[nextY][nextX]) {
visited[nextY][nextX] = 1;
queue.push([nextY, nextX]);
}
});
}
town.push(numOfHouse);
}
}
town.sort((a, b) => a - b);
console.log(town.length);
console.log(town.join("\n"));
}
// 실행
solution();