숨바꼭질 1697

문제

접근 방법

BFS로 풀면 된다. BFS 안에 1칸 앞 또는 뒤로 이동한 경우, 2배 순간 이동한 경우를 넣으면 된다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
					시작												목표

초기 상태는 이럴 것이다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
				1	0	1				1							목표

첫 번째는 이럴 것이고

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
			2	1	0	1	2	2	2	1	2			2			목표

두 번째는 이럴 것이다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
		3	2	1	0	1	2	2	2	1	2	3	3	2	3	3	목표	3

세 번째는 이럴 것이고
네 번째에는 목표에 도달할 것이다.

중복되는 경우를 제외해주어야 한다는 것을 알게 될 것이다. 앞으로 놓을 값은 이전에 놓은 값에는 가지 못하는 것이다. (당연하지만 이전에 놓인 값이 더 낮다)

코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int map[100001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(map, 0x3f, sizeof(map));
    queue<int> bfs;
    int N, K;
    cin >> N >> K;
    bfs.push(N);
    map[N] = 0;
    while (!bfs.empty())
    {
        int cur = bfs.front();
        bfs.pop();
        if (cur == K)
        {
            cout << map[cur];
            exit(0);
        }
        if (cur + 1 <= 100000)
        {
            if (map[cur + 1] > map[cur] + 1)
            {
                map[cur + 1] = map[cur] + 1;
                bfs.push(cur + 1);
            }
        }
        if (cur - 1 >= 0)
        {
            if (map[cur - 1] > map[cur] + 1)
            {
                map[cur - 1] = map[cur] + 1;
                bfs.push(cur - 1);
            }
        }
        if ((cur << 1) <= 100000)
        {
            if (map[cur << 1] > map[cur] + 1)
            {
                map[cur << 1] = map[cur] + 1;
                bfs.push(cur << 1);
            }
        }
    }
    return 0;
}

풀이

실수로 push 하는 것을 조건문 밖에 두었다. 그렇게 되면 무수히 많은 중복된 경우 때문에 메모리 초과가 뜬다. 조심해야 한다.