백준 node.js 16987번 계란으로 계란치기 백트래킹 JavaScript JS

풀이 방법

1. dfs를 통한 백트래킹 문제입니다.
2. 코드는 아래와 같습니다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const N = +input.shift();
const data = input.map((v) => v.split(" ").map(Number));
const eggsState = data.map((v) => v[0]);
let answer = 0;
dfs(0, eggsState);
console.log(answer);

function dfs(index, arr) {
  //순회를 마치면 탈출
  if (index === N) {
    const count = arr.filter((v) => v === false).length;
    if (answer < count) {
      answer = count;
    }
    return;
  }
  //깨진 상태면 다음 인덱스로 넘기기
  if (!arr[index]) {
    dfs(index + 1, [...arr]);
    return;
  }
  // 깨지지 않은 상태라면 모든 계란에 한 번씩 부딛히기
  let pass = false;
  for (let i = 0; i < N; i++) {
    if (i !== index && arr[i]) {
      pass = true;
      dfs(index + 1, hit(index, i, [...arr]));
    }
  }
  // 던질 대상 계란이 존재하지 않는 경우
  if (!pass) {
    if (answer < N-1) {
      answer = N-1;
    }
    return;
  }
}

function hit(a, b, state) {
  const [D1, W1] = [state[a],data[a][1]];
  const [D2, W2] = [state[b],data[b][1]];

  state[a] = D1 - W2 > 0 ? D1 - W2 : false;
  state[b] = D2 - W1 > 0 ? D2 - W1 : false;

  return state;
}

---

문제를 풀기 전날 계속해서 실패를 했었는데, 어디가 문제인지 모르겠더라고요. 엣지 케이스도 찾기 어려운 문제여서 고생을 했습니다. 다음날 마음을 가다듬고 처음부터 새로 푸니까 한번에 풀리네요…

오늘의 교훈

문제가 안 풀리면 끙끙대지 말고 다음날 풀자. 대부분 바로 풀린다🤣