[백준] 1941 소문난 칠공주 : 자바스크립트(node.js)

https://www.acmicpc.net/problem/1941

 

문제

총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

 

출력

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

 

예제 입력 1

YYYYY
SYSYS
YYYYY
YSYYS
YYYYY

 

예제 출력 2

2

 

 

풀이 방법

그러니까 이 문제는 

1. 5x5 배열에서 7개를 뽑아서

2. 이 7개가 인접해야만 하고

3. 4개 이상의 "S"를 포함하고 있어야

한다...

 

요령 모르겠고 일단 조합으로 25개 중 7개를 뽑아보자

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24

 

이렇게 위치를 생각하고 조합을 돌린다

여기서 좌표를 생각하려면 (n%5, n/5)라고 생각하면 된당

let select = new Array(7);

const pick = (idx, sIdx) => {
  if (sIdx === 7) {
    // 다음 조건 할 일 수행
    return;
  }

  if (idx === 25) {
    return;
  }

  select[sIdx] = idx;
  pick(idx + 1, sIdx + 1);
  pick(idx + 1, sIdx);
};

idx : 내가 뽑을 숫자들, sIdx : 총 몇개를 뽑았는지

 

sIdx === 7 인 상황 : 뽑을거 다 뽑은 상황

idx === 25인 상황 : 더이상 뽑을 숫자가 없는 상황

 

pick(idx + 1, sIdx + 1); : 이번 숫자 뽑고 다음숫자로 넘어가기

pick(idx + 1, sIdx); : 이번숫자 안뽑고 다음숫자로 넘어가기

 

 

그럼 이제 저 7개가 뽑힌 상황에서 그 7개가 인접하는지, 4개 이상의 S를 포함하는지 확인한다

인접 여부는 bfs를 돌려버리기

const isAdjacent = (array) => {
  let visited = new Array(7).fill(false);

  let queue = new Array();
  queue.push(array[0]);
  visited[0] = true;
  let cnt = 1;

  const dx = [0, 1, 0, -1];
  const dy = [1, 0, -1, 0];

  while (queue.length !== 0) {
    const cur = queue.shift();
    const cx = cur % 5;
    const cy = Math.floor(cur / 5);
    for (var i = 0; i < 4; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];
      if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
        for (var j = 0; j < 7; j++) {
          if (
            array[j] % 5 == nx &&
            Math.floor(array[j] / 5) == ny &&
            !visited[j]
          ) {
            cnt++;
            visited[j] = true;
            queue.push(array[j]);
          }
        }
      }
    }
  }
  if (cnt === 7) return true;
  else return false;
};

 

자꾸 자바스크립트의 나누기는 몫이 아니라 정말 나누기,,, 소수점까지 나온다는걸 간과한다

Math.floor를 자꾸 까먹엉,,,,

 

7개의 숫자가 들어있는 array를 전달받으면 

일단 빈 배열에 array[0]를 집어넣고 카운트를 1로 한 뒤 이걸 큐라고 생각하면서 while로 bfs를 돌렸다

shift로 큐의 맨 앞의 값을 빼내 dx dy로 해당 위치의 인접 4방 좌표를 확인하고

이 좌표들이 array에 있는 요소들이라면 방문처리 + 큐에 집어넣기

그리고 카운트를 늘린다

그러니까 붙어있는 요소가 있으면 카운트를 늘리는 방식인거

 

큐에 들어있는걸 다 뺐을 때 카운트가 7이라면 모든 곳이 붙어있다는거니까 true 반환하고

7이 아니라면 방문하지 못한곳 존재 = 인접하지 않음 => false 반환

 

이제 얘네가 S를 4개 이상 포함하는지 확인하기

는 간단

const checkSY = (array) => {
  let cnt = 0;
  for (var i = 0; i < 7; i++) {
    const cur = array[i];
    if (arr[cur % 5][Math.floor(cur / 5)] === "S") cnt++;
  }
  if (cnt >= 4) return true;
  else return false;
};

 

..그냥 숫자카운트

 

아 

arr이건 입력받은 배열임

 

위의 두 함수에서 모두 true를 반환받은 경우 answer를 늘려준다

나름? 시간을 고려해서 checkSY를 먼저 확인하게 했다

bfs 먼저보는거보다 저거 먼저 봐서 거르는게 더 빠르지 않나...? 아님말고

 

 

코드를 다 합치면 다음과 같다

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((e) => e.split(" ").map(String));

let answer = 0;
let select = new Array(7);
let arr = new Array(5);

const isAdjacent = (array) => {
  let visited = new Array(7).fill(false);

  let queue = new Array();
  queue.push(array[0]);
  visited[0] = true;
  let cnt = 1;

  const dx = [0, 1, 0, -1];
  const dy = [1, 0, -1, 0];

  while (queue.length !== 0) {
    const cur = queue.shift();
    const cx = cur % 5;
    const cy = Math.floor(cur / 5);
    for (var i = 0; i < 4; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];
      if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
        for (var j = 0; j < 7; j++) {
          if (
            array[j] % 5 == nx &&
            Math.floor(array[j] / 5) == ny &&
            !visited[j]
          ) {
            cnt++;
            visited[j] = true;
            queue.push(array[j]);
          }
        }
      }
    }
  }
  if (cnt === 7) return true;
  else return false;
};

const checkSY = (array) => {
  let cnt = 0;
  for (var i = 0; i < 7; i++) {
    const cur = array[i];
    if (arr[cur % 5][Math.floor(cur / 5)] === "S") cnt++;
  }
  if (cnt >= 4) return true;
  else return false;
};


const pick = (idx, sIdx) => {
  if (sIdx === 7) {
    if (checkSY(select) && isAdjacent(select)) {
      answer++;
    }
    return;
  }

  if (idx === 25) {
    return;
  }

  select[sIdx] = idx;
  pick(idx + 1, sIdx + 1);
  pick(idx + 1, sIdx);
};

const solution = () => {

  for (var i = 0; i < 5; i++) {
    arr[i] = input[i][0].split("");
  }
  pick(0, 0);
  console.log(answer);
};

solution();

 

1. 입력에서 헤매고

2. 나누기에서 헤매고

3. 조합에서 idx === 24로 처음에 쓰는바람에 빙빙 헤맸다 바보,,,,