[백준 알고리즘] Node.js 2667. 단지번호붙이기

1. 문제

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

2667번: 단지번호붙이기

 

2. 풀이

1) BFS로 푼 풀이

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +inputs.shift();
const graph = inputs.map(v => v.split('').map(vv => +vv));
const visited = Array.from({length : N}, () => Array(N).fill(0));
let homeArr = [];

const bfs = (x,y) => {
  const dx = [-1,1,0,0]; //이동 가능 경로
  const dy = [0,0,-1,1];
  let cnt = 1; // 초기 cnt 설정

  const queue = [[x,y]];

  visited[x][y] = 1; // 방문처리
    
  while(queue.length){
    const [sx,sy] = queue.shift();

    for(let i = 0; i < 4; i++){
      const nx = sx + dx[i]; // 이동한 부분
      const ny = sy + dy[i];

      if(nx >= 0 && ny >= 0 && nx < N && ny < N){
        if(graph[nx][ny] && !visited[nx][ny]){
          visited[nx][ny] = 1; // 방문처리
          cnt++; // 방문했으니까 cnt 증가
          queue.push([nx,ny]); // 다음 방문할 위치
        }
      }
    }
  }

  return cnt;
}

/** 
graph[i][j] 가 1 이면서 방문했던 기록이 없는 부분만 순회하며 
마지막에 cnt를 돌려받아 homeArr에 담아둠.
*/
for(let i = 0; i < N; i++){
  for(let j = 0; j < N; j++){
    if(graph[i][j] && !visited[i][j]) homeArr.push(bfs(i,j))
  }
}

console.log(`${homeArr.length}\n${homeArr.sort((a,b) => a-b).join('\n')}`)

 

 

2) DFS로 푼 풀이(stack)

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +inputs.shift();
const graph = inputs.map(v => v.split('').map(vv => +vv));
const visited = Array.from({length : N}, () => Array(N).fill(0));
const homeArr = [];

const dfs = (x,y) => {
  const dx = [-1,1,0,0];
  const dy = [0,0,-1,1];
  const stack = [[x,y]];
  let cnt = 1;

  visited[x][y] = 1;

  while(stack.length){
    const [sx,sy] = stack.pop();

    for(let i = 0; i < 4; i++){
      const nx = sx + dx[i];
      const ny = sy + dy[i];

      if(nx >= 0 && ny >= 0 && nx < N && ny < N){
        if(graph[nx][ny] && !visited[nx][ny]){
          visited[nx][ny] = 1;
          cnt++;
          stack.push([nx,ny])
        }
      }
    }
  }

  return cnt;
}

for(let i = 0; i < N; i++){
  for(let j = 0; j < N; j++){
    if(graph[i][j] && !visited[i][j]){
      homeArr.push(dfs(i,j))
    }
  }
}
console.log(`${homeArr.length}\n${homeArr.sort((a,b) => a-b).join("\n")}`)

 

3. 정리

- stack은 후입선출(LIFO), queue는 선입선출(FIFO).

- dfs에서는 stack을, bfs에서는 queue를 이용한다고 알고 있어서 stack에는 pop()을, queue에는 shift()를 사용.

- 근데 큰 차이는 없는 거 같음.  dfs + 재귀를 사용하는 방법도 있다고 한다.

- DFS BFS 너무 어렵당