[class3] (백준 1697) 숨바꼭질

문제

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

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

입력

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

출력

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

제한

 

예제 입력 1

5 17

예제 출력 1

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

W3sicHJvYmxlbV9pZCI6IjE2OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMjhcdWJjMTRcdWFmMmRcdWM5YzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIxOFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWIzZDlcdWMwZGRcdWFjZmMmbmJzcDtcdWMyMjhcdWJjMTRcdWFmMmRcdWM5YzhcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMjE4XHViZTQ4XHVjNzc0XHViMjk0IFx1ZDYwNFx1YzdhYyBcdWM4MTAgTigwICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHViM2Q5XHVjMGRkXHVjNzQwIFx1YzgxMCBLKDAgJmxlOyBLICZsZTsgMTAwLDAwMClcdWM1ZDAmbmJzcDtcdWM3ODhcdWIyZTQuJm5ic3A7XHVjMjE4XHViZTQ4XHVjNzc0XHViMjk0IFx1YWM3N1x1YWM3MFx1YjA5OCBcdWMyMWNcdWFjMDRcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjMjE4XHViZTQ4XHVjNzc0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBYXHVjNzdjIFx1YjU0YyBcdWFjNzdcdWIyOTRcdWIyZTRcdWJhNzQgMVx1Y2QwOCBcdWQ2YzRcdWM1ZDAgWC0xIFx1YjYxMFx1YjI5NCBYKzFcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjMjFjXHVhYzA0XHVjNzc0XHViM2Q5XHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMVx1Y2QwOCBcdWQ2YzRcdWM1ZDAgMipYXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWJlNDhcdWM3NzRcdWM2NDAgXHViM2Q5XHVjMGRkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMyMThcdWJlNDhcdWM3NzRcdWFjMDAgXHViM2Q5XHVjMGRkXHVjNzQ0IFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YmE4NyBcdWNkMDggXHVkNmM0XHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHViZTQ4XHVjNzc0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNTggTlx1YWNmYyBcdWIzZDlcdWMwZGRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtOXHVhY2ZjIEtcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzIxOFx1YmU0OFx1Yzc3NFx1YWMwMCBcdWIzZDlcdWMwZGRcdWM3NDQgXHVjYzNlXHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjMjE4XHViZTQ4XHVjNzc0XHVhYzAwIDUtMTAtOS0xOC0xNyBcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHViYTc0IDRcdWNkMDhcdWI5Y2NcdWM1ZDAgXHViM2Q5XHVjMGRkXHVjNzQ0IFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTY5NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhdGNoIFRoYXQgQ293IiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgYmVlbiBpbmZvcm1lZCBvZiB0aGUgbG9jYXRpb24gb2YgYSBmdWdpdGl2ZSBjb3cgYW5kIHdhbnRzIHRvIGNhdGNoIGhlciBpbW1lZGlhdGVseS4gSGUgc3RhcnRzIGF0IGEgcG9pbnQgTiAoMCAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIG9uIGEgbnVtYmVyIGxpbmUgYW5kIHRoZSBjb3cgaXMgYXQgYSBwb2ludCBLICgwICZsdDs9IEsgJmx0Oz0gMTAwLDAwMCkgb24gdGhlIHNhbWUgbnVtYmVyIGxpbmUuIEZhcm1lciBKb2huIGhhcyB0d28gbW9kZXMgb2YgdHJhbnNwb3J0YXRpb246IHdhbGtpbmcgYW5kIHRlbGVwb3J0aW5nLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPldhbGtpbmc6IEZKIGNhbiBtb3ZlIGZyb20gYW55IHBvaW50IFggdG8gdGhlIHBvaW50cyBYLTEgb3IgWCsxIGluIGEgc2luZ2xlIG1pbnV0ZTxcL2xpPlxyXG5cdDxsaT5UZWxlcG9ydGluZzogRkogY2FuIG1vdmUgZnJvbSBhbnkgcG9pbnQgWCB0byB0aGUgcG9pbnQgMipYIGluIGEgc2luZ2xlIG1pbnV0ZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JZiB0aGUgY293LCB1bmF3YXJlIG9mIGl0cyBwdXJzdWl0LCBkb2VzIG5vdCBtb3ZlIGF0IGFsbCwgaG93IGxvbmcgZG9lcyBpdCB0YWtlIGZvciBGYXJtZXIgSm9obiB0byByZXRyaWV2ZSBpdD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBLPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBUaGUgbGVhc3QgYW1vdW50IG9mIHRpbWUsIGluIG1pbnV0ZXMsIGl0IHRha2VzIGZvciBGYXJtZXIgSm9obiB0byBjYXRjaCB0aGUgZnVnaXRpdmUgY293LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGZhc3Rlc3Qgd2F5IGZvciBGYXJtZXIgSm9obiB0byByZWFjaCB0aGUgZnVnaXRpdmUgY293IGlzIHRvIG1vdmUgYWxvbmcgdGhlIGZvbGxvd2luZyBwYXRoOiA1LTEwLTktMTgtMTcsIHdoaWNoIHRha2VzIDQgbWludXRlcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 2번

• 문제를 번역한 사람: author6
• 데이터를 추가한 사람: cohan, djm03178

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

bool visited[100001];
int shortTime[100001];

int BFS(int N, int goal)
{
    queue<int> q;
    q.push(N);
    shortTime[N] = 0;
    visited[N] = true;
    while (!q.empty())
    {
        int temp = q.front();
        if (temp == goal)
            break;
        q.pop();

        if ((temp + 1) >= 0 && (temp + 1) < 100001 && !visited[temp + 1])
        {
            visited[temp + 1] = true;
            q.push(temp + 1);
            shortTime[temp + 1] = shortTime[temp] + 1;
        }
        if ((temp - 1) >= 0 && (temp - 1) < 100001 && !visited[temp - 1])
        {
            visited[temp - 1] = true;
            q.push(temp - 1);
            shortTime[temp - 1] = shortTime[temp] + 1;
        }
        if ((temp * 2) >= 0 && (temp * 2) < 100001 && !visited[temp * 2] )
        {
            visited[temp * 2] = true;
            q.push(temp * 2);
            shortTime[temp * 2] = shortTime[temp] + 1;
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, K;
    cin >> N >> K;
    BFS(N, K);
    cout << shortTime[K];
    return 0;
}