[JS/백준]{BFS,DFS,재귀함수}(2638) 단지번호붙이기

문제 설명

지도를 하나씩 검사하다가 아파트인것과 동시에 방문한 적이없는 위치에서 bfs,dfs를 돌리면서

아파트의 갯수를 카운팅하고 완료되면 아파트갯수를 배열에 넣어주는 방식으로 풀수있는 문제이다.

예전에는 bfs방식으로 풀었는데 최근에 백트래킹에 dfs와 재귀함수가 필요해서 dfs와 재귀함수를

공부하기 위해서 dfs와 재귀함수 방식으로 다시 풀었다.

풀이 코드

예전에 푼 BFS 방식

function bfs(startX, startY) {
  let dx = [-1, 1, 0, 0],
    dy = [0, 0, -1, 1];

  let q = [[startX, startY]];

  visited[startX][startY] = 1;

  let apartCnt = 1;

  while (q.length) {
    let [x, y] = q.shift();

    for (let k = 0; k < 4; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];

      if (0 <= nx && 0 <= ny && nx < n && ny < n) {
        if (board[nx][ny] === 1 && visited[nx][ny] === 0) {
          q.push([nx, ny]);
          visited[nx][ny] = 1;
          apartCnt++;
        }
      }
    }
  }
  return apartCnt;
}

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

const n = +input[0];
const board = input.slice(1).map((str) => str.split("").map(Number));

let visited = Array.from(Array(n), () => new Array(n).fill(0));

const result = [];
let apart = 0;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (board[i][j] === 1 && visited[i][j] === 0) {
      result.push(bfs(i, j));
      apart++;
    }
  }
}

console.log(apart);

result.sort((a, b) => a - b);
result.forEach((val) => console.log(val));

DFS, 재귀함수 방식

function dfs(x, y) {
  if (0 <= x && 0 <= y && x < n && y < n) {
    if (!visited[x][y] && board[x][y]) {
      apartCnt++;
      visited[x][y] = true;
      for (let k = 0; k < 4; k++) {
        dfs(x + dx[k], y + dy[k]);
      }
    }
  }
}

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

const n = +input[0];
const board = input.slice(1).map((str) => str.trim().split("").map(Number));
let visited = Array.from(Array(n), () => new Array(n).fill(false));

const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];

const apartArr = [];
let apartCnt = 0;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (board[i][j] === 1 && !visited[i][j]) {
      dfs(i, j);
      apartArr.push(apartCnt);
      apartCnt = 0;
    }
  }
}
apartArr.sort((a, b) => a - b);
console.log(apartArr.length);
apartArr.forEach((val) => console.log(val));