[C++] 백준/Gold/12852. 1로 만들기 2

문제: 1로 만들기 2 (백준 12852번)

문제 분석

주어진 정수 x를 아래 연산 세 가지를 사용하여 1로 만드는 최소 연산 횟수를 구하고, 그 과정에서 거친 수열(경로)도 출력하는 문제이다.
가능한 연산은:

• x가 3으로 나누어 떨어지면 3으로 나눈다.
• x가 2로 나누어 떨어지면 2로 나눈다.
• x에서 1을 뺀다.

BFS(너비 우선 탐색)를 활용하면 최단(최소 연산) 경로를 자연스럽게 찾을 수 있으며, 각 단계에서 이전 상태(부모 노드)를 기록하면 경로 재구성이 가능하다.

---

해결 방법

BFS 탐색을 통한 경로 찾기

시작점: 입력받은 x를 시작 노드로 한다.

• 방문 기록: visited 배열(혹은 벡터)을 사용해 각 숫자에 도달한 직전 노드를 저장한다.
• 연산 적용: 현재 노드에 대해,
  • 만약 2로 나누어 떨어진다면 node/2를,
  • 만약 3으로 나누어 떨어진다면 node/3을,
  • 그리고 node-1을
    아직 방문하지 않았다면 방문 처리하고, 부모를 기록하면서 큐에 넣는다.

경로 재구성

• BFS가 1에 도달하면, visited 배열을 이용해 1부터 시작해 역으로 부모 노드를 따라가며 경로를 구성한다.
• 최종적으로 경로를 역순으로 출력하면 x에서 1로 가는 경로가 된다.

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int x; 
    cin >> x;
    // visited[i]는 i에 도달하기 직전의 노드를 저장 (경로 추적용)
    vector<int> visited(x + 1, 0);
    queue<int> bfs;
    bfs.push(x);
    visited[x] = x;  // 시작 노드의 부모는 자기 자신으로 초기화

    while (!bfs.empty()) {
        int node = bfs.front();
        bfs.pop();
        if (node == 1) break;
        // 2로 나누기 연산
        if (node % 2 == 0 && !visited[node / 2]) {
            visited[node / 2] = node;
            bfs.push(node / 2);
        }
        // 3으로 나누기 연산
        if (node % 3 == 0 && !visited[node / 3]) {
            visited[node / 3] = node;
            bfs.push(node / 3);
        }
        // 1 빼기 연산
        if (!visited[node - 1]) {
            visited[node - 1] = node;
            bfs.push(node - 1);
        }
    }
    
    // 경로 재구성: 1부터 시작하여 부모를 따라 x까지 도달
    vector<int> result;
    int cur = 1;
    while (true) {
        result.push_back(cur);
        if (cur == x) break;
        cur = visited[cur];
    }
    
    // 연산 횟수는 경로 길이 - 1
    cout << result.size() - 1 << "\n";
    // 경로를 역순으로 출력 (x → ... → 1)
    for (auto it = result.rbegin(); it != result.rend(); it++) {
        cout << *it << " ";
    }
}