[백준][13549번] 숨바꼭질 3[cpp, c++]

백준 13549 숨바꼭질3

• bfs 문제이다.
• 기존 숨바꼭질과 로직이 살짝 다르다.
• https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

• 풀이방법
  1) 순간이동의 시간은 0초니깐 순간이동 먼저 큐에 넣어준다.
  2) 배열의 범위와 MAX값을 잘 설정한다.
  3) MAX값이 2배가 됐을 때 배열에 담길 수 있는 크기여야한다.

#include<iostream>
#include<queue>
using namespace std;
queue<pair <int, int>> q;
bool check[2000000];
int N, K;
void bfs() {
    while (!q.empty()) {
        int x = q.front().first;
        int time = q.front().second;
        check[x] = true;
        q.pop();

        if (x == K) { //도착
            cout << time << "\n";
            break;
        }
        //순간이동
        int x3 = 2 * x;
        if (x3 >= 0 && x3 <= 200000 && check[x3] == false) {
            q.push(make_pair(x3, time));
            check[x3] = true;
        }

        // -1 
        int x1 = x - 1;
        if (x1 >= 0 && x1 <= 200000 && check[x1] == false) {
            q.push(make_pair(x1, time + 1));
            check[x1] = true;
        }
        // +1 
        int x2 = x + 1;
        if (x2 >= 0 && x2 <= 200000 && check[x2] == false) {
            q.push(make_pair(x2, time + 1));
            check[x2] = true;
        }
    }
}

int main(void) {
    cin >> N >> K;
    q.push(make_pair(N, 0));
    bfs();
    return 0;
}