Gidhub BE Developer

[BOJ] 13594. 숨바꼭질3

2018-09-21
goodGid
Algorithm

Problem

Problem URL : 숨바꼭질3

[1] Answer Code (18. 09. 21)

#include <iostream>
#include <queue>
using namespace std;

int visit[100001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int st,dest;
    cin >> st >> dest;
    
    if( st == dest ){
        cout << "0"  << endl;
        return 0;
    }
    
    queue<pair<int,int>> q;
    q.push({st,0});
    
    int ans = 2e9;

    while (! q.empty()) {
        int size = (int) q.size();
        
        for(int i=0; i<size; i++){
            int top = q.front().first;
            int _time = q.front().second;
            q.pop();
            
            if( top == dest ){
                ans = ans > _time ? _time : ans;
                continue;
            }
            
             /*
             // [1]
              if( visit[top] ) // Already Visit
                 continue;
            */
            
            visit[top] = 1;
            
            if( top - 1 >= 0 && !visit[top - 1] )  // Already Visit
                q.push( {top - 1, _time + 1});
            
            if(top + 1 <= 100000 && !visit[top + 1] )  // Already Visit
                q.push( {top + 1, _time + 1});
            
            if(top * 2 <= 100000 && !visit[top * 2] )  // Already Visit
                q.push( {top * 2, _time });
            
        } // end of for i
    } // end of while
    
    cout << ans << endl;
    
    return 0;
}

Review

  • [1]을 넣게되면 다음과 같은 경우 틀리게 된다.
1 4 일 때

순서가 
현재 위치에서
+ x - 순서일 때

1 2 4 // [1]
 + x
1 2 4 // [2]
 x x


[1]으로 할 땐 
+로 2가된 상태가 되면 이동값이 1이 된다. 
그리고 2는 visit 상태로 바뀐다.

그런데 x(곱하기)로 된 2가 된 상태를 살펴보려고하면 
이미 visit했기 때문에 continue가 된다.

하지만 실제로 답은 x를 통해 2가된 값이
최종적으로는 0번의 움직으로 목적지에 도착할 수 있다.

[2] Answer Code (18. 09. 23)

#include <iostream>
#include <queue>
#define p pair<int,int>
using namespace std;

int v[100001]; // v is visit

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int st, dest;
    cin >> st >> dest;

    queue<p> q;
    q.push({st,0});
    
    int ans = 2e9;
    while (! q.empty()) {
        int top = q.front().first;
        int time = q.front().second;
        q.pop();
        
        if(top == dest){
            ans = ans < time ? ans : time;
            continue;
        }
        
        v[top] = 1;
        if( top + 1 < 100001 && !v[top+1] ){
            q.push({top+1, time+1});
        }
        if( top - 1 > -1 && !v[top-1]){
            q.push({top-1, time+1});
        }
        if( top * 2 < 100001 && !v[top*2]){
            q.push({top*2, time});
        }
    }
    
    cout << ans << endl;
    return 0;
}

Recommend

Index