백준 1697] C++ 숨바꼭질

해당 문제는 백준 사이트에서 풀 수 있습니다.

 

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

 

1. 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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초만에 동생을 찾을 수 있다.

출처

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

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

 

 

 

 

 

 

2. 조건

1. 수빈이는 동생에게 가기위해 1초에 이동할 수 있는 경우의 수는 3가지이다.

2. 수빈이의 위치를 X라고 둘 때 1초 동안 갈 수 있는 곳은 X + 1, X - 1, X * 2 총 3가지이다.

3. 수빈이가 동생에게 갈 수 있는 가장 빠른 시간은 몇초인가?

 

3. 풀이

bfs로 풀면 간단하게 풀 수 있습니다.

수빈이가 갈 수 있는 모든 방법들 ( X + 1, X - 1, X * 2 )를 큐에 모두 때려 박고

동생 위치가 나올 때 까지 계속 돌리면서 가장 먼저 일치하는 값이 나오면 해당 값에 대한 cost값을

구하면 됩니다.

 

왜냐면 bfs의 특징은 너비탐색이기 때문에 각 최단 위치에서 갈 수 있는 범위를 탐색하는 것이기 때문입니다.

(이해가 잘 안가시려나?....)

 

여튼 저는 여기에 bool을 만들어 중복 검사를 막아줬습니다.

왜냐면 같은 값이 나오게 된다면 같은 작업을 또 반복하기 때문이죠.

 

4. 코드

 

#include <iostream>
#include <vector>
#include <queue>

#pragma warning(disable: 4996)

using namespace std;

bool isCheck[100010];

int main() {
    int T;
    int N, M, K;
    int X, Y;
    int answer = 0;

    cin >> N >> K;
    queue<pair<int, int>> q;
    q.emplace(N, 0);
    
    while (!q.empty()) {
        int locate = q.front().first;
        int cost = q.front().second;
        q.pop();
        
        if (locate == K) {
            answer = cost;
            break;
        }

        int x_1 = locate - 1;
        int x_2 = locate + 1;
        int x_3 = locate * 2;


        if (0 <= x_1 && !isCheck[x_1]) {
            isCheck[x_1] = true;
            q.emplace(x_1, cost + 1);
        }

        if (x_2 <= K && !isCheck[x_2]) {
            isCheck[x_2] = true;
            q.emplace(x_2, cost + 1);
        }

        if (x_3 <= K + 1 && !isCheck[x_3]) {
            isCheck[x_3] = true;
            q.emplace(x_3, cost + 1);
        }
    }

    cout << answer << endl;
    return 0;
}