유기농 배추 (백준 코딩테스트 1012번, DFS/BFS, NodeJS 풀이)

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

 

 

문제 유형:

DFS/BFS

 

문제 요약:

모든 배추를 수호하려면 지렁이를 몇 마리 풀어야 하나?

(=좌표 상에 이어져있는 배추 그룹이 몇 개가 있는가?)

 

입출력 예 (입력 / 출력):

개인적으로 입/출력은 한 입력 당 테스트 케이스 하나만 전달해줬음 좋겠다... 연달아 나오는 여러 개의 테스트 케이스 입력값을 분리하는거 자체가 고역이다.

 

문제 풀이 전략:

1. 배추밭을 맵핑한다.

2. 배추밭에 배추가 있는 좌표를 기록한다.

3. dfs선회로 이어져 있는 배추를 모두 방문처리한다.

4. 이어져 있는 배추 그룹 당 한 번 씩 '카운터 += 1'을 해준다.

 

내 풀이:

et fs = require("fs");
let input = fs.readFileSync("input.txt").toString().trim().split("\n");

const tcNum = input[0]; // 테스트 넘버
const condIdx = []; // "10 10 6" 같이 되어있는 조건 문장의 인덱스를 보관
const conditions = input.filter((arg, i) => { // 조건 문장을 필터링하여 보관
  // 조건 문장
  const args = arg.split(" ");
  if (args.length === 3) {
    condIdx.push(i);
    return arg;
  }
});

for (let tc = 0; tc < tcNum; tc++) {
  //테스트 케이스 횟수 만큼 반복
  let [xSpan, ySpan, cabNum] = conditions[tc].split(" "); // 조건 문장에서 변수 얻기
  
  /* 2차원 배열 범위를 구하는 파트 */
  const span = []; 
  for (let y = 0; y < ySpan; y++) {
    // 세로 행 반복
    span.push([]);
    for (let x = 0; x < xSpan; x++) {
      // 가로 행 반복
      span[y].push(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
  ...
  */
  
  
  /* 배추 위치를 기록하는 파트 */
  for (let i = condIdx[tc] + 1; i < input.length; i++) {
    // 조건 문장의 인덱스 + 1 부터 3마디 나오기 전까지
    if (input[i].split(" ").length === 3) {
      break;
    } else {
      const [x, y] = input[i].split(" ").map(Number);
      // console.log(x, y);
      span[y][x] = 1;
    }
  }
  /*
  이런 식으로 기록된다.
  1 1 0 0 0 0 0 0 0
  0 1 0 0 1 0 0 0 0
  0 0 0 0 1 0 0 0 0
  0 0 1 1 0 0 0 0 0
  ...
  */

  
  /* DFS 함수 선언*/
  function dfs(y, x) {
    if (cabNum === 0) return;
    if (y > -1 && span[y][x]) {
      span[y][x] = 2; // 방문했으면 1을 2로 바꿔준다. (방문 처리)
      // console.log(span[y][x]);
      cabNum--;
      if (span[y][x + 1] === 1) {
        // 우측으로 이동 가능?
        dfs(y, x + 1); // 우측으로 ㄱㄱ
      }
      if (span[y + 1] && span[y + 1][x] === 1) {
        // 아래로 이동 가능?
        dfs(y + 1, x); // 아래로 ㄱㄱ
      }
      if (span[y][x - 1] === 1) {
        // 좌측으로 이동 가능?
        dfs(y, x - 1); // 좌측으로 ㄱㄱ
      }
      if (y - 1 > -1 && span[y - 1][x] === 1) {
        //위로 이동 가능?
        dfs(y - 1, x); // 위로 ㄱㄱ
      }
    }
  }
  
  /* 2차원 배열을 순회하며 방문처리가 안 된 곳이라면 지렁이를 푸는 파트*/
  let cnt = 0; // 순회하는 횟수
  for (let j = 0; j < ySpan; j++) {
    for (let i = 0; i < xSpan; i++) {
      if (span[j][i] === 1) {
        // 만약 1이면
        dfs(j, i); // 순회 시작.
        cnt++; // 순회를 했으니 카운터++
      }
    }
  }
  /*
    순회가 시작하면 주변에 있는 접근 가능한(1인) 인자는 모두 2로 바꿔지기 때문에,
    순회가 시작할 때만 카운터를 높일 수 있다. 즉 5번을 움직일 수 있다.
  */
  console.log(cnt);
}

BFS로 푸는 것보다 DFS가 더 쉬워서 DFS로 풀었다. (BFS 공부도 더 해봐야할 듯...)