백준 1697번 숨바꼭질

문제

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

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

입력

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

출력

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

 

 

간단한 DFS 문제라고 생각하고 풀었는데 생각보다 답이 잘 안나왔고, 그 이유는 영역의 범위가 너무 커서 깊이 탐색으로 조졌다가는 시간초과를 피할 수 가 없었다. 

최대한 시간초과를 줄일만한 조건을 첨가해 줬는데 그 때 실수 한 것은 count가 K값보다 작아야 한 다는 점. 하지만 만약 K가 0이고 N이 10000부터 내려가야 하는 상황이라면 영영 K를 찾을 수 없다.

따라서 그 조건만 제거 해 주고 BFS로 고쳐 푸니 간단히 풀렸다.

 

 

#include<iostream>
#include<queue>
using namespace std;
 
 
int arr[100001];
 
int result;
int N, K;
 
 
int main(void)
{
    
    cin >> N >> K;
    
    
    for(int i =0; i<= 100000; i++)
    arr[i] = 987654321;
    
    result = 987654321;
    
    queue<pair<int,int> > que;    
    que.push({N,0});
        
    while(!que.empty())
    {
        
        
        int now = que.front().first;
        int count = que.front().second;
        
        //cout << now <<" "<<count << endl;
        
        que.pop();
        
        if(now == K && result > count)
        {
            result = count;
            continue;
        }
        
        
        
        
        if(now < 0 || now > 100000  || result < count)
        {
            
        }
        else if(arr[now] > count){
            
        
            
            
            arr[now] = count;
        
            
            if(now > K)
            {
                que.push({now-1,count+1});
            }
            else{
                
                que.push({now*2,count+1});
                que.push({now+1,count+1});
                que.push({now-1,count+1});
            }
            
            
        }
       
        
        
        
        
        
        
        
        
    }
    
    
    
    
    
    
    
    
    
    cout << result <<endl;
    
    
    
    
}

 

 

 

<DFS로 구현>

 

#include<iostream>
#include<map>
 
using namespace std;
 
int N, K , result;
int m[100001];
    
void DFS(int now ,int count)
{
    
    
    
    
    if(now < 0 || now > 100000  || result < count)
    return;
    
    
    if(m[now] < count)
    return;
    
    m[now] = count;
    
    
 
    if(result > count & now == K)
    {
        result = count;
        return;
        
    }
    
    if(now > K)
    {
        DFS(now-1,count+1);
    }
    else{
        
        DFS(now*2,count+1);
        DFS(now+1,count+1);
         
         DFS(now-1,count+1);
        
    }
    
    
        
    
    
    
    
    
    
    
}
 
int main(void)
{
    
        
    cin >> N >> K;
    
    
    result = 987654321;
    
    for(int i =0; i<=100000; i++)
    {
        m[i] = 987654321;
    }
    
    DFS(N,0);
    
    
    
    
    cout <<result<<endl;
    
}