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

백준 DFS 알고리즘 2667번_단지번호붙이기

난이도 : 실버I

 

문제 설명

문제 풀이 : 이 문제도 기본 DFS 유형을 요구하는 문제이다. 그래프 전체를 순회하면서 방문하지 않았다면 (이 문제에서 1과 0은 아파트의 위치이면서 방문여부로도 활용할 수 있다.) DFS를 호출한다. 여기서 DFS내부적으로 재귀를 부를때마다 선언해둔 글로벌 변수(home)를 한개씩 카운트 해주면서 같은 단지내의 아파트 개수를 세려주고 DFS함수 호출이 끝나면 하나의 단지를 탐색한 것이기 때문에 순서대로 배열에 넣어주면된다.

이후 정렬을 하고 길이 출력을 통해 단지 개수를 파악하고 배열값을 출력하면서 단지내 아파트 개수를 출력하면 된다.

 

//실버1 단지번호붙이기
const solution = () => {
  let cnt = []; //단지별 아파트 개수를 담는 배열

  //이중그래프 전체 탐색
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      //방문한적 없다면 DFS호출
      if (graph[i][j] === 1) {
        DFS(i, j);
        //DFS가 한번 수행되고 나면 하나의 단지 전체 방문처리 완료
        //전역 변수로 사용한 home을 배열에 넣고 초기화
        cnt.push(home);
        home = 0;
      }
    }
  }

  console.log(cnt.length);
  cnt.sort((a, b) => a - b); //오름차순 정렬
  cnt.map((el) => console.log(el)); //map함수로 순회
};

const DFS = (i, j, a) => {
  //범위 안에 속하고 방문처리가 되지 않았을때
  if (RangeCheck(i, j) && graph[i][j] === 1) {
    graph[i][j] = 0; //방문처리
    home += 1;
    for (let k = 0; k < dx.length; k++) {
      DFS(i + dx[k], j + dy[k]);
    }
  }
};

//그래프(배열) 범위 검증
function RangeCheck(i, j) {
  if (i >= 0 && i < n && j >= 0 && j < n) {
    return true;
  } else return false;
}

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
let graph = [];
let n = 0;
let home = 0; //단지별 아파트 개수
let dx = [1, -1, 0, 0];
let dy = [0, 0, 1, -1];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  n = input.shift();
  graph = Array.from(Array(n), () => new Array(n));

  //입력값을 그래프에 담아줌
  for (let i = 0; i < n; i++) {
    graph[i] = input[i].split("").map((el) => Number(el));
  }
  solution();
  process.exit();
});

 

* DFS 기본적인 문제를 몇개 풀다보니 패턴이 금방보이고 쉽게 파악할 수 있게 되었다.

각각의 문제마다 약간의 예외를 고려해줘야하지만 대부분 로직은 일정하게 이루어진것 같다.

이 문제에서 시간이 좀 오래걸린것은 재귀 호출시 카운트를 해줘야하는데 어떻게 해줘야할지 잘 몰라서

고민하다가 시간이 오래 지났다.  DFS 인자로 변수를 넣어주고 카운트 할려했지만 잘 안되서 결국엔 편하게 글로벌 변수를 이용했다.

DFS를 공부할때 재귀를 이용할줄만 알았지 재귀 자체를 다루는 법은 미숙한 것 같다. 따로 공부가 필요한것 같다.