1697. 숨바꼭질

1. 해결방법

• 수빈이 처음 위치(N)에서 BFS 돌리기 (BFS 돌리면 최단거리 나오기 때문)

 

2. Solution

#include <iostream>
#include <queue>

#define endl "\n"
#define MAX 100000+1
using namespace std;

int dx[] = {-1, 1};

int N, K;
bool visited[MAX];

void Input()
{
    cin >> N >> K;
}

void BFS(int X)
{   
    queue<pair<int, int> > q;
    q.push(make_pair(X, 0));
    visited[X] = true;

    while(!q.empty())
    {
        int x = q.front().first;
        int t = q.front().second;
        q.pop();

        if(x == K)
        {
            cout << t << endl;
            return;
        }

        for(int i = 0; i < 2; i++)
        {
            int nx = x + dx[i];
            if(nx >= 0 && nx <= MAX)
            {
                if(!visited[nx])
                {
                    q.push(make_pair(nx, t+1));
                    visited[nx] = true;
                }
            }
        }

        if(x*2 < MAX)
        {
            if(!visited[x*2])
            {
                q.push(make_pair(x*2, t+1));
                visited[x*2] = true;
            }
        }

    }
}

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

    Input();
    BFS(N);

    return 0;
}

 

3. 알아야 할 개념

• MAX 값 설정 (100000 + 1)

#define MAX 100000 + 1

 

• BFS 코드 떠올리기 Tip!

1. 반복되는 트리를 While문으로 구현
2. 부모노드 값을 기억해서 1)자식노드계산, 2)자식노드 queue 삽입