jinux127
Jinux
jinux127
  • 분류 전체보기 (109)
    • 엘리스 SW 엔지니어 트랙 (6)
      • TIL (6)
    • 개발지식 (22)
      • React (4)
      • JavaScript (9)
      • Web (4)
      • Node.js (1)
      • TypeScript (4)
    • 알고리즘 (69)
      • 백준 (47)
      • 프로그래머스 (14)
      • 이것이 코딩테스트다 (6)
    • 프로젝트 (10)
      • PHOTOCALENDAR (3)
      • 빙수먹을래? (7)
    • Life (0)
      • 헬스 (0)
      • 독서 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 블로그 이전

인기 글

태그

  • node.js
  • CSS
  • 알고리즘
  • 구현
  • 문법
  • 그리디

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
jinux127

Jinux

알고리즘/백준

[boj 2667] 단지번호붙이기 -js

2022. 3. 13. 18:50
// 단지번호붙이기

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
jinux127
jinux127

티스토리툴바