🎲 백준 18809번

백준 18809번

💊 정답을 봐도 로직이 똑같은데 대체 왜 틀리지 엄청 고민했다.. 정말 막막했는데 다행히 찾아냈다 후우..
if (visited[pointY][pointX][0] === "F") continue;
queue에 들어간 배열 중 "F"로 바뀐 애들이 있을텐데 이걸 처리를 안해주고 있었다...

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
const [N, M, G, R] = input.shift().split(" ").map(Number);
const garden = input.map((el) => el.split(" ").map(Number));

let answer = 0;

const bfs = (green, red) => {
 const visited = Array.from(new Array(N), () =>
   Array.from(new Array(M), () => ["1", 0])
 );

 let flower = 0;
 const dir = [
   [0, 1],
   [0, -1],
   [1, 0],
   [-1, 0],
 ];
 const queue = [];

 for (let g of green) {
   const Y = Math.floor(g / M);
   const X = g % M;
   visited[Y][X][0] = "G";
   queue.push([Y, X, 0]);
 }

 for (let r of red) {
   const Y = Math.floor(r / M);
   const X = r % M;
   visited[Y][X][0] = "R";
   queue.push([Y, X, 0]);
 }

 while (queue.length) {
   const [pointY, pointX, time] = queue.shift();
   if (visited[pointY][pointX][0] === "F") continue;
   for (let d = 0; d < 4; d++) {
     const [nextY, nextX] = [pointY + dir[d][0], pointX + dir[d][1]];
     if (
       nextY < 0 ||
       nextX < 0 ||
       nextY >= N ||
       nextX >= M ||
       visited[nextY][nextX][0] === "F" ||
       garden[nextY][nextX] === 0
     )
       continue;

     if (visited[nextY][nextX][0] === "1") {
       visited[nextY][nextX] = [visited[pointY][pointX][0], time + 1];
       queue.push([nextY, nextX, time + 1]);
     } else if (
       (visited[nextY][nextX][0] === "G" &&
         visited[pointY][pointX][0] === "R") ||
       (visited[nextY][nextX][0] === "R" && visited[pointY][pointX][0] === "G")
     ) {
       if (visited[nextY][nextX][1] === time + 1) {
         visited[nextY][nextX] = ["F", time + 1];
         flower++;
       }
     }
   }
 }
 return flower;
};

const visited = new Array(N * M).fill(false);

const dfs = (index, green, red) => {
 if (green.length === G && red.length === R) {
   const flower = bfs(green, red);
   if (answer < flower) {
     answer = flower;
   }
   return;
 }

 for (let i = index; i < N * M; i++) {
   if (visited[i]) continue;
   const Y = Math.floor(i / M);
   const X = i % M;
   if (garden[Y][X] === 2) {
     visited[i] = true;
     green.push(i);
     dfs(i, green, red);
     green.pop();
     red.push(i);
     dfs(i, green, red);
     red.pop();
     visited[i] = false;
   }
 }
};

dfs(0, [], []);
console.log(answer);