백준)1697-숨박꼭질

문제링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---------------------------------------------------------------------------------------------------------------------

풀이

수빈이는 3개의 능력을 이용하여 동생을 찾을수 있다. 각 능력의 해당하는 능력치로 이동할수 있는 방법을

만들어 주고 이문제 역시 BFS 로 문제 를 해결하기 위해서 방문 유무 를 설정 해주 어야한다 . 

단 주의할점은 순간이동을 사용한다음 뒤로 가는 경우가 더 빨리 동생을 찾을 수 있으므로 방문 하는 배열-

의 크기를 2배만큼 크게 선언해  주었다.

-----------------------------------------------------------------------------------------------------------------------

#include<iostream>
#include<queue>
using namespace std;
queue<int >q ;
int visited[200002]; // 수진이가 스킬을 쓰면 두배를  넘을수 있어서 배열 크기를 그만큼 선언.
int main()
{
    int i,j;
    int N , K;
    
    cin >> N >> K ;
    
    visited[N]=1; // 수진이가 출발하는 위치 를  다시 돌아 오지 않게위해 1로마킹.
    
    q.push(N);
    
    
    while(!q.empty())
    {
        int cur = q.front();
            q.pop();
        
        if(cur == K) //동생을 만남.
            break;
        
        int back  = cur - 1 ;
        
        int front = cur + 1 ;
        
        int skill = cur*2;
        
        if( back >=0 && back <= 100000 && !visited[back] )
        {
            visited[back] = visited[cur] + 1;
            
            q.push(back);
        }
        
        
        if( front >=0 && front <= 100000 && !visited[front] )
        {
            visited[front] = visited[cur] + 1;
            
            q.push(front);
        }
        
        if( skill >=0 && skill <= 100000 && !visited[skill] )
        {
            visited[skill] = visited[cur] + 1;
            
            q.push(skill);
        }
        
    }
    
    
    cout << visited[K]-1; //처음 수진이의 위치를 1로 해주어서 1을 빼주어야한다.
    
    return 0;
}