[백준 1697] 숨바꼭질

하루에 하나 알고리즘

누군가에게 조금이라도 도움이 됫으면 하는 바램으로 이 글을 작성합니다

제일 기초적인 알고리즘입니다.

풀이시간 : 5분

한번만에 맞추어서 기분이 좋네요

더 빨리 처리하는 방법이 있을텐데 그냥 문제의 조건만 넣어도 풀리는 문제 였습니다.

#include <iostream>
#include <queue>
using namespace std;
int n, k;
queue<int> q;
int visit[100001] = { 0, };
int ans=0;
//bfs
void bfs(int go)
{
    visit[go] = 1;
    q.push(go);
    int cnt = 0;
    while (!q.empty())
    {
        int x = q.front();
        //도착했을 경우 멈춤.
        // go의 위치에서 이동하지 않았는데 멈추었으므로 정답은 -1 을 해줌
        if (x == k)
        {
            ans = visit[x]-1;
            break;
        }
        q.pop();
        // 문제에서 각 조건들 체크 후 q 삽입
        if (x - 1 >= 0 && visit[x - 1] == 0)
        {
            visit[x - 1] = visit[x] + 1;
            q.push(x - 1);
        }
        if (x + 1 <= 100000 && visit[x + 1] == 0)
        {
            visit[x + 1] = visit[x] + 1;
            q.push(x + 1);
        }
        if (x * 2 <= 100000 && visit[2 * x] == 0)
        {
            visit[x * 2] = visit[x] + 1;
            q.push(x * 2);
        }
        
    }
}
int main()
{
    cin >> n >> k;
    bfs(n);
    cout << ans << endl;
    return 0;
}