백준 2667번:: 단지번호붙이기

Kim Young Jae·2022년 10월 4일
0

백준 알고리즘

목록 보기
4/4

[2667번: 단지번호붙이기 (acmicpc.net)]

풀이

모든 좌표를 탐색하면서 방문했던 곳은 방문처리하고 DFS 방식으로 연산을 하면 될 것 같다.
현재 좌표에서 상하좌우를 검색하고 아직 방문을 하지 않았으면 방문 처리를 하여 더 이상 방문할 곳이 없을때까지 수행한다.
이 수행 횟수를 저장하여 출력하면 될 것 같다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");

const board = input.map((el) => el.split(""));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
let cnt = 1;
let answer = [];

function DFS(x, y) {
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];

    if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1) {
      board[nx][ny] = 0;
      cnt++;
      DFS(nx, ny);
    }
  }
}

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (board[i][j] == 1) {
      board[i][j] = 0;
      DFS(i, j);
      answer.push(cnt);
      cnt = 1;
    }
  }
}
console.log([answer.length, ...answer.sort((a, b) => a - b)].join("\n"));
profile
프론트엔드 뭐시기 주로 하는 사람

0개의 댓글