[백준2667_자바스크립트(javascript)] - 단지번호붙이기

🔴 문제

단지번호붙이기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

const map = inputs.map((it) => it.split(''));

function dfs(x, y) {
  if (x < 0 || y < 0 || x >= n || y >= n) return false;
  if (map[x][y] === '1') {
    map[x][y] = cnt;
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
    return true;
  }
  return false;
}

let cnt = 2;
for (let i = 0; i < Number(n); i++) {
  for (let j = 0; j < Number(n); j++) {
    if (dfs(i, j)) {
      cnt += 1;
    }
  }
}
const answer = [];
const flatMap = map.flat().filter((it) => it !== '0');
for (let i = 2; i < cnt; i++) {
  answer.push(flatMap.filter((it) => it === i).length);
}

answer.sort((a, b) => a - b);
console.log(cnt - 2);
for (const ans of answer) {
  console.log(ans);
}

🟢 풀이

연결된 영역의 개수를 구하는 문제이므로 dfs 유형이다.
나는 방문체크를 할때 방문체크를 하는 배열을 따로 만들지 않고(귀찮음) 입력받은 맵으로 방문체크까지 한다.
현재 문제에서 0은 집이 없는곳 1은 집이 있는곳이니까 cnt라는 변수를 2로 설정해두고 dfs 한 번돌때 방문한 곳은 cnt로 변경해준다.
0인곳은 집이 없고 집이 있는데 방문한 곳은 cnt 변수로 바뀌었으니 우리는 1일경우만 깊이우선탐색을 진행해주면 된다.
전체 집 방문이 끝나면 내 맵은 0, 2, 3, ⋯ 이 숫자들로 차 있을텐데 이 2차원 배열을 돌면서 2가 몇개인지, 3이 몇개인지 세어주기 위해 배열을 펴준다. 이 과정에서 쓸모없는 0도 필터링 해줬다.

const flatMap = map.flat().filter((it) => it !== '0');

그 후 하나의 단지에 집이 몇 개인지 세어주었는데 풀이를 적다보니 너무 더러운 코드 같다.
2부터 cnt까지 순회하면서 매번 필터링을 하는 O(n2)의 코드를 짜주었는데 길이가 cnt+1인 빈 배열을 생성해 0으로 초기화 해주고 배열을 한 번 순회하면서 i가 2일때 2번 인덱스 값 증가, i가 3일때 3번 인덱스 값 증가시켜주는 계수정렬(O(n))을 사용하는 것이 맞는듯 그럼 마지막에 정렬해서 값을 출력해줄때도 편해진다^^*

🔵 Ref