[백준] 12852 : 1로 만들기 2

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

---

• 3가지 경우의 수에 대해서 BFS 를 통해 최소 거리를 구할 수 있고, 연산 도중 문자열을 통해 경로를 저장해나가며 풀 수 있다.
• DP 로 풀 수도 있는데, 2 부터 N 까지 각 위치까지의 최소 경로를 저장해나가며 반복한다.
• 현재 위치 i + 각 케이스 별 (이전까지의 최소 경로 + 현재까지의 경로) 들 중 최소 경로가 i 의 최소 경로가 된다.

---

#include <iostream>
#include <queue>

using namespace std;

int N, temp, count;
int visited[1000001];

int main(void)
{
    cin >> N;
    queue<pair<int, string>> q;
    q.push({N, ""});

    while(true)
    {
        int sz = q.size();
        for(int s = 0 ; s < sz ; s++)                               // bfs
        {
            int cur = q.front().first;
            string answer = q.front().second;
            q.pop();

            if(cur == 1)                                            // 1 에 도착할 시
            {
                cout << count << endl << answer + "1" << endl;      // 연산 횟수 및 경로 출력 후 종료
                return 0;
            }

            temp = cur-1;
            if(!visited[temp])                                      // 3번 케이스
            {
                visited[temp] = true;
                q.push({temp, answer + to_string(cur) + " "});
            }
            if(cur % 2 == 0)                                        // 2번 케이스
            {
                temp = cur / 2;
                if(!visited[temp])
                {
                    visited[temp] = true;
                    q.push({temp, answer + to_string(cur) + " "});
                }
            }
            if(cur % 3 == 0)                                        // 1번 케이스
            {
                temp = cur / 3;
                if(!visited[temp])
                {
                    visited[temp] = true;
                    q.push({temp, answer + to_string(cur) + " "});
                }
            }
        }
        count++;
    }
}