[BOJ] 1697

숨바꼭질

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

분류

• Silver 1

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

해법

큐를 이용한 BFS방식으로 가장 먼저 동생의 위치에 도달하는 것의 level을 찾으면 됩니다.
메모이제이션을 사용하지 않는다면 메모리 초과가 납니다.

정답 코드

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

int main(void)
{
    int N, K;
    scanf(" %d %d", &N, &K);
    int levelMemo[100001] = {0, }; // for memoization
    queue<int> q;
    q.push(N);
    while (true)
    {
        int cur = q.front(); q.pop();
        if (cur == K)
        {
            printf("%d", levelMemo[cur]);
            return 0;
        }

        if (cur - 1 >= 0 && levelMemo[cur - 1] == 0) // walk left
        {
            q.push(cur - 1);
            levelMemo[cur - 1] = levelMemo[cur] + 1;
        } 
        if (cur + 1 <= 100000 && levelMemo[cur + 1] == 0) // walk right
        {
            q.push(cur + 1);
            levelMemo[cur + 1] = levelMemo[cur] + 1;
        }
        if (cur * 2 <= 100000 && levelMemo[cur * 2] == 0) // warp
        {
            q.push(cur * 2);
            levelMemo[cur * 2] = levelMemo[cur] + 1;
        } 
    }
    return 0;
}