백준 node.js 1941번 소문난 칠공주 백트래킹 JavaScript JS

1941번: 소문난 칠공주

문제풀이 방법

1. 25명중 무작위로 7명을 뽑습니다.
2. 7명중 4명 이상이 ‘이다솜파’라면 dfs함수를 실행합니다.
3. dfs함수는 무작위로 뽑힌 7명이 인접한 자리에 앉아있는지 확인하는 함수입니다. dfs를 활용하여 인접한지 확인할 수 있습니다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
  .map((v) => v.split(""));

let answer = 0;
select7([], 0);
console.log(answer);

function dfs(group) {
  const next = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
  ];
  const visited = Array.from({ length: 5 }, () => Array(5).fill(false));
  for (let [y, x] of group) {
    visited[y][x] = true;
  }
  const [y, x] = group[0];
  visited[y][x] = false;
  const stack = [[y, x]];
  let pass = 0;
  while (stack.length !== 0) {
    const [a, b] = stack.pop();
    for (let [a2, b2] of next) {
      if (a + a2 >= 0 && a + a2 < 5 && b + b2 >= 0 && b + b2 < 5) {
        if (visited[a + a2][b + b2]) {
          stack.push([a + a2, b + b2]);
          visited[a + a2][b + b2] = false;
        }
      }
    }
    pass++
  }
  if (pass === 7) return true;
  return false;
}

function select7(stack, number) {
  const len = stack.length;
  if (len - number > 3) {
    return;
  }
  if (len === 7) {
    if (number >= 4) {
      if (dfs([...stack])) {
        answer++;
      }
    }
    return;
  }
  const [a, b] = stack[len - 1] || [-1, -1];
  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      if ((i === a && j > b) || i > a) {
        if (input[i][j] === "S") {
          select7([...stack, [i, j]], number + 1);
        } else {
          select7([...stack, [i, j]], number);
        }
      }
    }
  }
}