[Algorithm] Baekjoon 12852번 : 1로 만들기 2

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

12852번: 1로 만들기 2

int dp[1000001];
int parents[1000001];
int n;
 
struct Node
{
    int num;
    int count;
};
 
void BFS()
{
    queue<Node> q;
    q.push({ n,0 });
    memset(dp, 0x3f, sizeof(dp));
    dp[n] = 0;
 
    while (!q.empty())
    {
        int curNum = q.front().num;
        int curCount = q.front().count;
        q.pop();
 
        if (curNum == 1)
        {
            cout << curCount << endl;
            return;
        }
 
        if (curNum % 3 == 0)
        {
            if (curCount + 1 < dp[curNum / 3])
            {
                dp[curNum / 3] = curCount + 1;
                parents[curNum / 3] = curNum;
                q.push({ curNum / 3,curCount + 1 });
            }
        }
 
        if (curNum % 2 == 0)
        {
            if (curCount + 1 < dp[curNum / 2])
            {
                dp[curNum / 2] = curCount + 1;
                parents[curNum / 2] = curNum;
                q.push({ curNum / 2, curCount + 1 });
            }
        }
 
        if (curCount + 1 < dp[curNum - 1])
        {
            dp[curNum - 1] = curCount + 1;
            parents[curNum - 1] = curNum;
            q.push({ curNum - 1,curCount + 1 });
        }
    }
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    BFS();
    int recurIndex = 1;
    vector<int> v;
 
    while (recurIndex != 0)
    {
        v.push_back(recurIndex);
        recurIndex = parents[recurIndex];
    }
 
    for (int i = v.size() - 1; i >= 0; --i)
    {
        printf("%d ", v[i]);
    }
}

그리디문제만 풀다가 다른 문제 감 잃을까봐 풀어본 DP문제이다.

특정 수를 1로 만들기 위한 조건 세가지가 있고, 최소의 횟수로 1을 만들어야 하는데 그럴 경우 그 중간경로까지 출력해야 하는 문제이다. 

실버1이고 정답률도 높길래 쉽나 싶다가도, DP문제에 워낙 약해서 좀 걸릴줄 알았는데, 확실히 아무리 예전이라도 비슷한 문제를 풀었던 기억이 어렴풋이 있어서 금방 풀긴 했다.

 

기본적으로 BFS로 진행하는데, 큐에 최대한 불필요한 노드를 넣는걸 방지한다.

조건을 만족한다고 바로 큐에 넣는게 아니라, DP테이블에 더 적은 횟수로 해당 수를 만들었던 기록이 있다면 큐에 넣지 않는다. 그런 기록이 없다면 큐에 넣고, DP테이블에 횟수를 새로 업데이트 해준다음 부모테이블에도 업데이트를 해준다.

마지막에 최소횟수의 경로를 출력해줘야 하기 때문이다.

 

꺼낸 노드의 num이 1이면 그대로 count를 출력 후 BFS는 종료해주고 부모테이블을 이용해 1부터 n까지의 경로를 출력해주면 된다.