🎲 백준 1941 소문난 칠공주

백준 1941번

💊 25개중 7개를 선택하고 이 후 조건에 맞는 것을 찾아야한다.
💊 나는 가로,세로 연결되어 있는지 확인할 때 bfs를 사용했다.
🎨 참고 코드
🎨 참고 코드

코드

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

let answer = 0;

const visited = new Array(25).fill(false);
const map = Array.from(new Array(5), () => new Array(5).fill(false));

const check = () => {
  let count = 0;
  const dir = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];

  const bfs = (y, x) => {
    const queue = [[y, x]];
    const visited = Array.from(new Array(5), () => new Array(5).fill(false));
    visited[y][x] = true;
    while (queue.length) {
      const [Y, X] = queue.shift();
      for (let d = 0; d < 4; d++) {
        const [nextY, nextX] = [Y + dir[d][0], X + dir[d][1]];
        if (
          nextY < 0 ||
          nextX < 0 ||
          nextY >= 5 ||
          nextX >= 5 ||
          visited[nextY][nextX] ||
          !map[nextY][nextX]
        )
          continue;
        queue.push([nextY, nextX]);
        visited[nextY][nextX] = true;
        count++;
      }
    }

    return count;
  };

  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      if (map[i][j]) {
        count++;
        return bfs(i, j);
      }
    }
  }
};

const dfs = (num, count, s) => {
  if (count === 7) {
    if (s >= 4 && check() === 7) answer++;
  } else {
    for (let i = num; i < 25; i++) {
      if (visited[i]) continue;
      visited[i] = true;
      const y = Math.floor(i / 5);
      const x = i % 5;
      let countS = s;
      map[y][x] = true;
      if (input[y][x] === "S") countS++;
      dfs(i, count + 1, countS);
      map[y][x] = false;
      visited[i] = false;
    }
  }
};

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