// 단지번호붙이기
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split(/\n/);
const N = parseInt(input.shift());
const map = [];
for(let i=0; i<N; i++){
map.push(input[i].split('').map(Number));
}
const sol = (N,map) =>{
// 상하좌우
const dx = [0,0,-1,1];
const dy = [1,-1,0,0];
const countHome = [];
let count = 0;
let home = 0;
const dfs = (x,y) =>{
if(x<0 || y<0 || x>=N || y>=N) return false;
if(map[x][y] === 1){
map[x][y] = 0;
home++;
for(let i=0; i<4; i++){
dfs(x+dx[i], y+dy[i]);
}
return true;
}
return false;
}
for(let i=0; i< N; i++){
for(let j=0; j<N; j++){
if(dfs(i,j)){
count++;
countHome.push(home);
home = 0;
}
}
}
console.log(count);
console.log(countHome.sort((a,b)=>a-b).join('\n'));
}
sol(N,map);
dfs를 활용해 풀었다.
1. 좌표를 탐색해 주변의 값들이 집인지 판단해 재귀호출하였다.
2. 재귀호출하며 집의 개수를 세고 한번 단지의 탐색을 마치면 단지의 개수를 올려주었다.
문제의 조건중 집의 수를 오름차순으로 정렬하여 출력하는 것을 잊어 조금 헤맸다..
'알고리즘 > 백준' 카테고리의 다른 글
[boj 2178] 미로탐색 -js (0) | 2022.03.14 |
---|---|
[boj 2178] 섬의 개수 -js (0) | 2022.03.13 |
[boj 11724] 이분 그래프 -js (0) | 2022.03.13 |
[boj 11724] 연결 요소의 개수 -js (0) | 2022.03.13 |
[boj 1260] DFS와 BFS -js (0) | 2022.03.13 |