[백준_2503] 숫자야구 ( 백트래킹 - 자바스크립트 )

문제

 

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

2503번: 숫자 야구

 

How to Solve ?

 

[1] 백트래킹

 

이 문제를 풀면서, 내가 완전탐색에 굉장히 취약 하다는 사실을 알게 되었다.

 

여태까지  완전 탐색에 대해서 내가 취하는 태도는 "그냥 탐색하면 되는거 아닌가?" 였었는데 ! 문제를 풀다보니 대부분 관련된 경우의 수를 모두 만들어두고 문제에서 제공하는 룰에 맞춰서 그 배열을 조절 하는 방식으로 해결이 되었다.

 

숫자야구" 게임에서 우리가 해야 하는 것은 " 숫자 물어봤을 때, 얻을 수 있는 스트라이크 & 볼의 카운트" 를 모두 충족하는 경우를 출력 해야함으로, 충족하는 값을 찾기 위해서는 3자리로 이루어진 모든 순열을 만들어야 한다.

 

그리하여, 나는 순열을 백트래킹을 통해 만들었고 만들어진 수를 바탕으로

 

1) "만들어진 수"와 주어진 값<123,356,327,489> 들의 볼카운트(b_cnt)의 값이 같은지 확인

 

2) "만들어진 수"와 주어진 값<123,356,327,489> 들의 스트라이크 카운트(s_cnt)의 값이 같은지 확인

 

을 아래와 같은 isBall, isStrike 함수를 사용 하여 확인을 하였고 충족하는 값들을 <ans> 배열에 담아서 문제를 해결 할 수 있었다.

 

function isBall(answer, hint) {
  let cnt = 0;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (i !== j) {
        if (answer[i] === hint[j]) cnt++;
      }
    }
  }
  return cnt;
}

function isStrike(answer, hint) {
  let cnt = 0;
  for (let i = 0; i < 3; i++) {
    if (answer[i] === hint[i]) cnt++;
  }
  return cnt;
}

function dfs(res, visit) {
  if (res.length === 3) {
    let flag = true;
    const answer = res.join("");
    
    
    for (const [hint, s, b] of hints) {
      
      const strHint = hint.toString();
      
      const strike = isStrike(answer, strHint);
      if (s !== strike) {
        flag = false;
        break;
      }
      
      const ball = isBall(answer, strHint);
      if (b !== ball) {
        flag = false;
        break;
      }
      
    }
    
    if (flag) ans.push(answer);
    return;
  }

  for (let i = 1; i <= 9; i++) {
  
    if (!visit[i]) {
      res.push(i);
      visit[i] = 1;
      dfs(res, visit);
      visit[i] = 0;
      res.pop();
    }
    
  }
  
}

let hints = [
  [123, 1, 1],
  [356, 1, 0],
  [327, 2, 0],
  [489, 0, 1],
];

const visit = Array(10).fill(0);
const ans = [];
dfs([], visit);
console.log(ans);