백준[node.js] > 2667번 단지번호붙이기

문제

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

 

풀이

일단 지도를 2차원배열 형태로 변환시켰고 이를 이용해서 단지별로 아파트를 묶었다. 

dfs를 이용해서 특정 아파트에서 갈수 있는 모든 아파트를 하나의 단지로 묶었고 그 과정에서 단지내의 아파트의 갯수를 확인했다.

그렇게 apartment 라는 array에 단지내의 아파트 갯수를 push 한뒤 다시 아파트갯수를 오름차순으로 정렬하여 문제의 답을 구할 수 있었다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let N = Number(input.shift());

// 지도 2차원 배열로 저장
let map = [];
// 단지별 집 수를 담을 배열
let apartment = [];

input.forEach((str) => {
    let line = str.split("").map((n) => Number(n));
    map.push(line);
});

// 단지내 아파트 갯수 count
let apartmentCnt = 0;

let recursive = (r, c) => {
    // 동서남북
    let diffRow = [0, 0, 1, -1];
    let diffCol = [1, -1, 0, 0];

    for (let direction = 0; direction < 4; ++direction) {
        let [nextRow, nextCol] = [r + diffRow[direction], c + diffCol[direction]];

        if (map[nextRow] && map[nextRow][nextCol] && map[nextRow][nextCol] === 1) {
            map[nextRow][nextCol] = 0;
            ++apartmentCnt;
            recursive(nextRow, nextCol);
        }
    }
};

for (let row = 0; row < N; ++row) {
    for (let col = 0; col < N; ++col) {
        if (map[row][col] === 1) {
            apartmentCnt = 1;
            map[row][col] = 0;
            recursive(row, col);
            apartment.push(apartmentCnt);
        }
    }
}

apartment.sort((a, b) => a - b);
console.log(String(apartment.length));
console.log(apartment.join("\n"));

 

후기

자주 접했던 문제 유형이라 쉽게 풀 수 있었다.