[백준] 2667 단지번호붙이기 - javascript
📌 문제
https://www.acmicpc.net/problem/2667
📌 풀이
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let ans = 0;
let n = Number(input[0]);
let board = new Array(n);
for (let i = 0; i < board.length; i++) {
board[i] = input[i + 1].split("").map(Number);
}
let visit = new Array(n);
for (let i = 0; i < visit.length; i++) {
visit[i] = new Array(n).fill(0);
}
let cnt_ans = [];
function BFS(x, y) {
let cnt = 1;
let queue = [];
let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];
queue.push([x, y]);
visit[x][y] = 1;
while (queue.length) {
let len = queue.length;
for (let i = 0; i < len; i++) {
let x = queue.shift();
for (let j = 0; j < 4; j++) {
let nx = x[0] + dx[j];
let ny = x[1] + dy[j];
if (
nx >= 0 &&
nx < n &&
ny >= 0 &&
ny < n &&
board[nx][ny] === 1 &&
visit[nx][ny] === 0
) {
visit[nx][ny] = 1;
queue.push([nx, ny]);
cnt++;
}
}
}
}
cnt_ans.push(cnt);
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === 1 && visit[i][j] === 0) {
BFS(i, j);
}
}
}
console.log(cnt_ans.length);
cnt_ans.sort((a, b) => a - b);
for (let i = 0; i < cnt_ans.length; i++) {
console.log(cnt_ans[i]);
}
✔ 알고리즘 : BFS
✔ BFS함수를 실행한 횟수가 구역의 수
✔ 방문체크를 위한 배열을 선언하고 board[i][j]가 1인데 방문처리가 안된집에서 부터 BFS탐색을 시작
✔ 구역안에서 queue에 push할때마다 집이 하나씩 증가하므로 cnt++ 해주고 BFS함수가 끝나기 전에 cnt를 ans_cnt에 push한다
✔ 구역의 개수는 ans_cnt.length
✔ 각 구역별 집의 수를 오름차순 정렬하여 출력
✔ 난이도 : 백준 기준 실버 1
Author And Source
이 문제에 관하여([백준] 2667 단지번호붙이기 - javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/백준-2667-단지번호붙이기-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)