[백준/JS] 16397

홓홓 디따 오랜만에 왔습니다..
이유는 무수한...시간초과들 속에서 오랜만에

얘를 봤기 때문이죠!끌끌~

암튼 문제 풀이해볼게용

문제

✏️ 문제풀이

일단 문제를 보면

N이라는 숫자가 G가 되어야 합니다.

모든 경우의 수를 봐야하므로 완전탐색을 이용해야 합니다.
맨 마지막 줄에 보면 버튼 누르는 횟수를 최소로 하고 싶다고 했으니까 그럼 뭐다???
BFS 쓰는 문제라는거죠

1. N 이 G 가 되어야 한다.
2. N을 조작하는 방법!
   2-1. N + 1
   2-2. N 에 2를 곱하고 0이 아닌 맨 앞자리 수에서 1을 빼준다.
   (이 경우 N에 2를 곱했을 때 99999가 넘어가면 안된다.)
3. N 유의사항
   3-1. N은 99999를 넘어가면 안된다.
   3-2. 버튼 누르는 횟수가 T를 넘어가면 안된다.

위 조건들을 고려해서 BFS를 짜주면 됩니다!

😅 여기서 내가 실수했던 것들

1. visited[N] 이 의미하는 것은 N이 되기까지 버튼을 누른 횟수라고 생각하면 됩니다.
   • 저는 착각해서 visited를 T만큼 만들고 true/false를 지정해서 버튼을 얼만큼 눌렀는지를 체크했습니다.
2. 버튼 누르는 횟수가 T와 동일하게 된다면 return 이 아닌 continue를 해서 탐색을 다시 진행할 것
3. 카운트를 1부터 센 것 (따라서 결과값에서 1 빼줘야 합니다.)
   • 요 문제점은 제가 visited 배열에 카운트를 직접 지정해주어서 그렇습니다.
   • 만일 queue 에 현재 노드값과 카운트를 넣는다면 0부터 넣어주면 문제 해결~입니다.

📝 결과코드

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

let [N, T, G] = input.shift().split(" ").map(Number);
let visited = new Array(100000).fill(0);

function bfs() {
  let queue = [[N]];//큐에는 현재 숫자를 넣어줌
  visited[N] = 1; //방문 여부 체크를 위해서 카운트를 1부터 시작함

  while (queue.length) {
    let [curNum] = queue.shift();

    //현재 숫자가 결과 값인 경우 반환
    if (curNum === G) {
      return;
    }

    //버튼을 누른 횟수가 T번을 넘어가면 다시 탐색
    // +1 해준 이유는 카운트 시작값이 1이라서
    if (visited[curNum] === T + 1) {
      continue;
    }

    // 1번째 숫자 조작 방법
    if (curNum + 1 <= 99999 && visited[curNum + 1] === 0) {
      queue.push([curNum + 1]);
      visited[curNum + 1] = visited[curNum] + 1;
    }

    //2번째 숫자 조작 방법
    if (curNum * 2 <= 99999 && curNum != 0) {
      let nextNum = curNum * 2;
      let first = nextNum.toString().split("").map(Number);
      first[0] -= 1;

      nextNum = Number(first.join(""));

      if (visited[nextNum] === 0) {
        visited[nextNum] = visited[curNum] + 1;
        queue.push([nextNum]);
      }
    }
  }
}

bfs();

//정답 -1 해주는 이유는 카운트 시작값이 1이었기 때문
visited[G] !== 0 ? console.log(visited[G] - 1) : console.log("ANG");