프로그래머스: 숫자 변환하기 (BFS)

숫자 변환하기

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성하기

제한 조건
1 ≤ x ≤ y ≤ $10^6$

문제 풀이 조건
1 ≤ n < y

알고리즘 구상하기

시간복잡도를 줄이는데 집중한다.
x에 수행할 수 있는 연산은 총 3가지로, y가 되기까지 시도하는 경우의 수를 수학적으로 계산하면 3 _ 3 _ 3…이 될 것이다.
이는 가지치기 형태의 그래프로 나타낼 수 있으며 가장 빠르게 y에 도달하는 경우를 구하기 위해 이 그래프를 탐색하는 방법을 사용할 수 있다.

적절한 자료구조: BFS
그래프를 탐색하는 알고리즘에는 크게 DFS와 BFS가 있다. DFS는 한 가지 경우의 수를 끝에 도달할 때까지 탐색하기 때문에 그래프의 너비가 크지 않다면 효율적이다. 그러나 이 문제의 경우 매 번 연산을 3번씩 수행해야 하기 때문에 탐색 깊이가 1칸 깊어질수록 너비는 3의 지수 그래프 만큼 넓어진다.
이에 따라 DFS보다는 너비 우선 탐색을 수행하는 BFS가 상대적으로 효율적이라 판단하여 BFS를 채택하였다.

효율적인 큐(queue)관리로 시간복잡도 저감
위의 내용을 토대로, 1차적으로 다음의 코드를 구현했다.

function solution(x, y, n) {
  const calculateList = ["n", "2", "3"];

  function calculator(target, currentValue) {
    if (target === "n") return currentValue + n;
    if (target === "2") return currentValue * 2;
    if (target === "3") return currentValue * 3;
  }

  const answerList = [];
  const visited = new Set();
  const queue = [[x, 0]];
  visited.add(x);

  while (queue.length > 0) {
    const [currentValue, tryCount] = queue.shift();
    if (currentValue === y) return tryCount;
    if (currentValue > y) break;

    calculateList.forEach((target) => {
      const result = calculator(target, currentValue);

      if (!visited.has(result) && result <= y) {
        visited.add(result);
        queue.push([result, tryCount + 1]);
      }
    });
  }
  return -1;
}

그러나 위 코드를 채점했을때 두 문제에서 시간초과로 인한 오답처리가 되었고 이에 따라 시간복잡도를 더 줄일 수 있는 부분을 고민했다.
그 결과, queue에서 이전 값을 꺼내는 shift 연산을 개선하는 방법, 방문 노드와 queue에 결과값을 넣기 전에 정답(y)인지 체크하도록 하여 불필요한 while 반복을 줄이는 방법 이 두 가지를 추려냈다.

우선 queue에서 shift로 요소를 꺼내는 방법은 매번 배열 index가 재정립되어야 한다. 이에 따라 후자의 방법 보다는 전자의 방법을 채택했을 때 시간복잡도를 상대적으로 크게 줄일 수 있으므로 전자의 방법을 먼저 시도했다.

queue는 선입선출의 원칙을 지키기 때문에 shift를 사용할 수 없다면 첫번째 요소에 접근하는 방법이 필요했다. 또한 while문의 반복 조건인 queue의 길이도 로직에 영향이 가지 않도록 고려해야 했다.

이에 따라 queue에서 요소를 빼내는 대신, 첫번째 요소부터 queue를 순회하며 동일한 깊이의 노드들에 대한 계산을 수행했다. 그리고 그 결과값, 즉, 다음 깊이의 노드들에 대한 값을 별도의 queue(newQueue)에 저장해두었다.

동일한 깊이의 노드들을 모두 방문했다면 이 newQueue의 요소들을 queue에 새롭게 할당하여 반복문 조건이 유지되도록 하였다.

이를 종합하여 수정한 2차 코드는 다음과 같으며 기존에 시간 초과로 통과하지 못한 문제를 해결할 수 있었다.

[JavaScript]

function solution(x, y, n) {
  const calculateList = ["n", "2", "3"];

  function calculator(target, currentValue) {
    if (target === "n") return currentValue + n;
    if (target === "2") return currentValue * 2;
    if (target === "3") return currentValue * 3;
  }

  const answerList = [];
  const visited = new Set();
  let queue = [[x, 0]];
  visited.add(x);

  while (queue.length > 0) {
    const newQueue = [];
    for (let i = 0; i <= queue.length - 1; i++) {
      const [currentValue, tryCount] = queue[i];
      if (currentValue === y) return tryCount;

      calculateList.forEach((target) => {
        const result = calculator(target, currentValue);

        if (!visited.has(result) && result <= y) {
          visited.add(result);
          newQueue.push([result, tryCount + 1]);
        }
      });
    }
    queue = [...newQueue];
  }
  return -1;
}