백준 1697 - 숨바꼭질

문제

 

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

1697번: 숨바꼭질

 

 

풀이

 

현재 위치 X에서 이동할 수 있는 세가지 방향인 X+1, X-1, X*2를 검사하고 K가 맞는지 확인한다. 만약 K가 아니라면

시간을 한번 증가시키고, K를 찾을 때까지 이 방식을 반복한다.

 

X+1, X-1, X*2를 한 단계에서 검사하기 위해 BFS 탐색의 개념을 이용한다.  현재 큐의 크기만큼 반복하면서 X+1, X-1, X*2를 검사하면 한 단계에서 세 위치를 모두 검사할 수 있다.

 

 

코드

 

#include <iostream>
#include <queue>
 
using namespace std;
 
bool graph[100001];
int N, K;
queue<int> q;
int cnt;
 
int nextX(int i, int x)
{
    if (i == 0) return x + 1;
    else if (i == 1) return x * 2;
    else return x - 1;
}
 
void bfs(int s)
{    
    q.push(s);
    graph[s] = true;
    
    while (!q.empty())
    {
        int len = q.size();
        
        while (len--)
        {
            s = q.front();
            q.pop();
 
            if (s == K) return;
 
            for (int i=0; i<3; i++)
            {
                int x = nextX(i, s);
                if (x >= 0 && x <= 100000)
                {
                    if (!graph[x])
                    {
                        q.push(x);
                        graph[x] = true;
                    }
                }
            }
        }
        cnt++;
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> K;
 
    bfs(N);
 
    cout << cnt;
 
    return 0;
}