Node.js) 백준 2667번 : 단지 번호 붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

하나의 집으로 이루어진 단지도 고려해야함.

 

input

2

10

01

 

answer

2

1

1

 

const fs = require('fs');
const [n,...arr] = fs.readFileSync("./dev/stdin").toString().trim().split("\n");
const N = +n;
const house = arr.map(v=>[...v.split(''),0].map(w=>+w));
house.push(new Array(N+1).fill(0))

const edge = [];
for(let y = 0; y<N; y++){
  for(let x =0; x<N; x++){
    let now = N*y+x;
    if(house[y][x]==1){
      if(house[y][x+1]==1){
        edge.push([now,now+1])
      }
      if(house[y+1][x]==1){
        edge.push([now,now+N])
      }
      if(house[y][x+1]==0 && house[y+1][x]==0){
        edge.push([now,now])
      }
    }
  }
}


let answer = []; 
let marked= []; 
let adj = []; 
for(let i =0; i<(N+1)*(N+1); i++){
  marked[i] = true; 
  adj[i] = [];
}


edge.forEach(v=>{
  adj[v[0]].push(v[1])
  adj[v[1]].push(v[0])
  marked[v[0]] = false;
  marked[v[1]] = false;
})

function bfs(s){
  let q = [];
  marked[s] = true;
  q.push(s);
  let result =1;
  while(q.length>0){
    let v =q.shift();
    adj[v].forEach(w=>{
      if(!marked[w]){
        marked[w]=true;
        result++;
        q.push(w)
      }
    })
  }
  return result;
}

function check(){
  for(let i = 0; i<marked.length; i++){
    if(marked[i]==false) return i
  }
  return -1;
}


let flag = check()
while(flag>-1){
  answer.push(bfs(flag));
  flag=check();
}
console.log(answer.length+'\n'+answer.sort((a,b)=>a-b).join('\n'))