[ 백준 _ 2667 ] 단지번호 붙이기 (DFS)

문제

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

2667번: 단지번호붙이기

 

How to Solve ?

 

이전에 "이취코" 에서 풀었던 음료수 얼려먹기와 같이 "특정 단지"를 찾아내고, 각 단지가 포함하는 호수를 찾는 문제이다.

최단 거리의 이동이 아니기에 다소 익숙한 DFS를 통한 문제 풀이를 하게 되었다.

 

function isValidRange(row, col) {
  if (row >= 0 && row < N && col >= 0 && col < N) {
    return true;
  }
  return false;
}

function DFS(row, col) {
  if (
    isValidRange(row, col) === true &&
    map[row][col] === 1 &&
    visited[row][col] === 0
  ) {
    visited[row][col] = 1;
    number++;

    for (let k = 0; k < 4; k++) {
      DFS(row + dx[k], col + dy[k]);
    }
  }
}

function solution() {
  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
      if (map[row][col] === 1 && visited[row][col] === 0) {
        DFS(row, col);
        complex.push(number);
        number = 0;
      }
    }
  }
  complex.sort((a, b) => a - b);
  const answer = [complex.length, ...complex];
  console.log(answer.join("\n"));
}

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

const complex = [];
let number = 0;


// 테스팅을 위한 인풋
let map = [
  [0, 1, 1, 0, 1, 0, 0],
  [0, 1, 1, 0, 1, 0, 1],
  [1, 1, 1, 0, 1, 0, 1],
  [0, 0, 0, 0, 1, 1, 1],
  [0, 1, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 0],
  [0, 1, 1, 1, 0, 0, 0],
];

let visited = [
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
];

let N = map.length;

solution();