Algorithm/백준
백준 2667 단지번호붙이기 (typescript, javascript)
GrapeMilk
2021. 9. 21. 16:42
백준에서 stdin의 파일을 읽을 때 윈도우에서는 '/r/n'을 해야하지만 백준에 제출할 떄는 개행 문자를 '/n'로 해야함...
import * as fs from 'fs';
const solution = (map: number[][]) => {
let houseIdx = 2;
const houseCntArr: number[] = [];
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const bfs = (x: number, y: number) => {
const queue: {
x: number;
y: number;
}[] = [];
queue.push({
x,
y,
});
let cnt = 0;
while (queue.length > 0) {
const cur = queue.shift();
const x = cur?.x ?? 10;
const y = cur?.y ?? 10;
if (map[x][y] === 1) {
map[x][y] = houseIdx;
cnt++;
} else {
continue;
}
for (let i = 0; i < 4; i++) {
const next = { x: x + dx[i], y: y + dy[i] };
if (
next.x >= 0 &&
next.y >= 0 &&
next.x < map.length &&
next.y < map.length &&
map[next.x][next.y] === 1
) {
queue.push(next);
}
}
}
houseCntArr.push(cnt);
houseIdx++;
};
for (let i = 0; i < map.length; i++) {
for (let j = 0; j < map.length; j++) {
if (map[i][j] === 1) {
bfs(i, j);
}
}
}
houseCntArr.sort((a, b) => a - b);
console.log(houseCntArr.length);
houseCntArr.map((val) => console.log(val));
};
const inputData = fs.readFileSync('dev/stdin').toString().split('\r');
const n = inputData.shift();
const mapInput = inputData.map((v) => {
return v.split('').map((v2) => +v2);
});
solution(mapInput);