[백준] 1697번 숨바꼭질

문제

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

풀이과정

이제부터 모든 문제를 제한시간 1시간을 두고 최대한 생각을 해보고나서 안될 것 같으면 검색을 해야겠다.
한시간이 되기 전에 이 문제가 주어지는 n을 n-1,n+1,n*2 로 나눠지는 트리를 만들어 depth를 출력하면 될 것 같다는 생각을 하게됐다.
하지만 생각처럼 구현을 하지 못했다.

이제는 슬슬 BFS, DFS가 이해되기 시작한다. 나중에 한 번 더 풀어봐야겠다

소스코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 200000

bool chk[200000]; // i에 방문했는지의 여부
int dist[200000]; // dist[i] i까지 가는데 걸린 비용

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

    int n, k;

    cin >> n >> k;

    queue<int> q;
    chk[n] = true;
    q.push(n);
    dist[n] = 0;

    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        int num[3] = { node - 1,node + 1,node * 2 };

        for (int i = 0; i < 3; i++)
        {
            if (num[i] >= 0 && num[i] < MAX)
            {
                if (chk[num[i]] == false)
                {
                    q.push(num[i]);
                    chk[num[i]] = true;
                    dist[num[i]] = dist[node] + 1;
                }
            }
        }

    }

    if (n == k) cout << 0 << "\n";
    else cout << dist[k] << "\n";

    return 0;
}