[백준 25418번] 정수 a를 k로 만들기 (C++)

문제링크 : https://www.acmicpc.net/problem/25418

25418번: 정수 a를 k로 만들기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int A, K;
int visited[1000001];

int bfs()
{
    queue<pii>q;
    q.push({A, 0});

    while(!q.empty())
    {
        auto[cur, cnt] = q.front();
        q.pop();
        
        if(cur == K) return cnt;

        if(cur+1 < 1000001 && !visited[cur+1]) //1을 더했을 경우 범위조건 + 방문 체크
        {
            visited[cur+1] = 1;
            q.push({cur+1, cnt+1});
        }

        if(cur*2 < 1000001 && !visited[cur*2]) //2를 곱했을 경우 범위조건 + 방문체크
        {
            visited[cur*2] = 1;
            q.push({cur*2, cnt+1});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> A >> K;
    cout << bfs();
    return 0;
}

 

경우의 수가 2가지 이므로 각각에 대해 체크를 해주어야 하는 bfs문제이다.

1를 더해주는 경우는 현재값에 1를 더해준 값이 최대값인 1000001을 넘는지, 또 이미 방문했던 값이 아닌지를 체크해준다.

둘다 무사히 통과하면 해당 값을 방문처리하고 큐에 해당값과 카운팅+1을 하여 같이 넘겨준다.

2를 곱해주는 경우도 거의 동일하다.

 

해당 문제에서 주의해야할점은 범위 조건을 체크해주어야 하는 것이다.

만약 cur+1이나, cur*2의 값이 최대값인 1000001을 넘어선다면 방문배열 체크할때 오류가 발생하게 된다.

그리고 이에따라 체크 순서 또한 범위조건이 방문배열 체크보다 무조건 앞에 와야 한다.