백준 node.js 18809번 Gaaaaaaaaaarden 백트래킹 JavaScript JS

18809번: Gaaaaaaaaaarden

풀이 방법

1. 배양액을 뿌릴 수 있는 케이스를 모두 찾습니다.
2. 케이스를 순회하며 꽃이 피는 개수를 BFS를 통해 구합니다.
3. DFS가 아닌 BFS로 구하는 이유는, 꽃이 핀다면 시간이 지나도 배양액은 흘러가지 않고, 꽃이 핀 자리에서 확산이 멈추기 때문입니다. 따라서 DFS로 구하면 정답을 구할 수 없다고 판단했습니다.
4. 아래 코드 주석을 통해 확인해주세요

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const [N, M, G, R] = input.shift().split(" ").map(Number);
const earlyLand = input.map((v) => v.split(" ").map(Number));
const landCase = [];
//배양액을 뿌릴 수 있는 경우의 좌표를 landCase에 넣는다.
findCase(-1, -1, [], []);
let answer = 0;

//배양액을 뿌릴 수 있는 케이스를 순회합니다.
for (let land of landCase) {
  // 땅의 상태를 표시하는 3차원 배열입니다. 각 자리에는 [G순서, R순서]의 배열이 들어갑니다.
  const landState = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => Array(2).fill(Infinity))
  );
	//BFS Queue구현
  const Q = [];
  for (let [y, x] of land.G) {
    landState[y][x][0] = 0;
    Q.push([y, x]);
  }
  for (let [y, x] of land.R) {
    landState[y][x][1] = 0;
    Q.push([y, x]);
  }
  let i = 0;
  const next = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
  ];
  let blossom = 0;
	//BFS시작
  while (Q.length > i) {
    const [a, b] = Q[i];
    i++;
    if(!landState[a][b]) continue;
    const [Gcount, Rcount] = landState[a][b];
		//상하좌우 확인
    for (let [a2, b2] of next) {
      const A = a + a2;
      const B = b + b2;
      if (
        A >= 0 &&
        A < N &&
        B >= 0 &&
        B < M &&
        landState[A][B] !== false &&
        earlyLand[A][B] !== 0
      ) {
        const [Gcount2, Rcount2] = landState[A][B];
        if (Gcount2 === Rcount2 && Gcount2 === Infinity) {
          if (Gcount === Infinity) {
            landState[A][B][1] = Rcount + 1;
            Q.push([A, B]);
          } else {
            landState[A][B][0] = Gcount + 1;
            Q.push([A, B]);
          }
        } else if (
          (Gcount2 === Infinity && Rcount2 === Gcount + 1) ||
          (Rcount2 === Infinity && Gcount2 === Rcount + 1)
        ) {
          blossom++;
          landState[A][B] = false;
        }
      }
    }
  }
  if(answer < blossom) answer = blossom
}
console.log(answer)

//케이스를 찾는 함수. 초록배양액, 빨강배양액의 좌표를 가진 객체를 landCase배열에 푸시한다.
function findCase(y, x, GLands, RLands) {
  const Glen = GLands.length;
  const Rlen = RLands.length;
  if (Glen === G && Rlen === R) {
    landCase.push({ G: GLands, R: RLands });
    return;
  }
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if ((i === y && j > x) || i > y) {
        if (earlyLand[i][j] === 2) {
          if (Rlen < R) findCase(i, j, GLands, [...RLands, [i, j]]);
          if (Glen < G) findCase(i, j, [...GLands, [i, j]], RLands);
        }
      }
    }
  }
}

---

꽤 복잡해 보이는 문제이지만 백트래킹의 전형적인 문제로 차근차근 풀면 어렵지 않은 문제였습니다.

문제 채점하는데 6분이 넘게 소요되었네요.. 🤣