[C++][백준 1697] 숨바꼭질(BFS)

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

풀이 (BFS)

3가지 선택지(*2, -1, +1)가 존재하므로 3갈래로 계속 나눠지는 그래프를 BFS로 탐색한다고 생각하면 된다

총 몇 초가 흘렀는지를 체크해야 하기 때문에 queue를 pair로 설정해주었다

 

제출 코드 (BFS)

#include <iostream>
#include <queue>
using namespace std;

bool visited[100001];
int bfs(int start, int target)
{
    queue<pair<int, int>> q;
    q.push(make_pair(0, start));
    visited[start] = true;

    while (!q.empty())
    {
        int cur = q.front().second;
        int t = q.front().first + 1;
        q.pop();

        if (cur * 2 == target || cur + 1 == target || cur - 1 == target)
            return t;

        if (cur < 50001 && !visited[cur * 2])
        {
            q.push(make_pair(t, cur * 2));
            visited[cur * 2] = true;
        }
        if (cur > 0 && !visited[cur - 1])
        {
            q.push(make_pair(t, cur - 1));
            visited[cur - 1] = true;
        }
        if (cur < 100000 && !visited[cur + 1])
        {
            q.push(make_pair(t, cur + 1));
            visited[cur + 1] = true;
        } 
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;
    cout << ((n == k) ? 0 : bfs(n, k));
}

n == k인 조건을 체크 안 해서 오답이 떴었는데... 그냥 main 함수 내에서 처리해 주는 식으로 수정했다