백준 13549] C++ 숨바꼭질3

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

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

1. 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 

수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 

순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

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

입력

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

출력

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

예제 입력 1 

5 17

예제 출력 1 

2

힌트

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

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: idiot mohana9 tagun11

2. 조건

1. 수빈이는 N 위치에서 동생이 있는 K위치까지 가려고 한다.

2. 수빈이는 위치 N에서 +1, -1 하면 1초가 걸린다.

3. 수빈이의 위치 N에서 순간이동( *2)를 하면 0초가 걸린다.

이때 가장 빠른 시간을 출력해라.

3. 풀이

이 문제 역시 숨바꼭질1, 숨바꼭질2와 비슷한 문제입니다.

단, 순간이동시 0초가 걸리는게 문제입니다.

여기서 우리는 각 비용별로 최소 비용이 들면서 가장 빠른 경로를 찾아야 합니다.

가장 빠른 경로를 찾을 땐 bfs를 이용하면 됩니다.

문제는 최소 비용입니다. 순간이동시 0초가 걸리니 말이죠.

그래서 저는 int isCost[] 라는 배열을 선언한 뒤, 

해당 위치에 cost비용이, 지금 계산된 cost비용보다 크다면 교체하는 식으로 구했습니다.

그리고 bfs를 통해 수빈이의 위치에 도착한 요소가 발생되면,

이미 queue안에는 최소로 갈 수 있는 여러 경로가 저장되어 있다는 뜻입니다.

따라서 queue안에 넣어둘 때마다 isCost[] 값을 최소 값으로 변경해 준다면, 쉽게 구할 수 있습니다.

코드를 보고 이해하시기 바랍니다.

P.S

코드를 보시면 if문 안에 if문이 있는데, isCost[] 값을 초기 값으로 999999으로 준다면,

if ( isCost[x_1] == 0 ) <- 요 작업을 안해줘도 됩니다.

하지만 int isCost[100010] 으로 해줬기 때문에 10만번 돌려서 셋팅해주면, 시간초과 날 것 같아서 저렇게 했습니다.

4. 코드

#include <iostream>

#include <vector>

#include <queue>

#pragma warning(disable: 4996)

using namespace std;

int isCost[100010];

int main() {

    int T;

    int N, M, K;

    int X, Y;

    int answer = 999999;

    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 (isCost[locate] != 0 && isCost[locate] < cost)

            continue;

        if (locate == K) {

            answer = isCost[locate];

            break;

        }

        int x_1 = locate - 1;

        int x_2 = locate + 1;

        int x_3 = locate * 2;

        if (0 <= x_1) {

            if (isCost[x_1] == 0) {

                isCost[x_1] = cost + 1;

                q.emplace(x_1, cost + 1);

            }

            else {

                if (isCost[x_1] > cost + 1) {

                    isCost[x_1] = cost + 1;

                    q.emplace(x_1, cost + 1);

                }

            }

        }

        if (x_2 <= K) {

            if (isCost[x_2] == 0) {

                isCost[x_2] = cost + 1;

                q.emplace(x_2, cost + 1);

            }

            else {

                if (isCost[x_2] > cost + 1) {

                    isCost[x_2] = cost + 1;

                    q.emplace(x_2, cost + 1);

                }

            }

        }

        if (x_3 <= K + 1) {

            if (isCost[x_3] == 0) {

                isCost[x_3] = cost;

                q.emplace(x_3, cost);

            }

            else {

                if (isCost[x_3] > cost) {

                    isCost[x_3] = cost;

                    q.emplace(x_3, cost);

                }

            }

        }

    }

    cout << answer << endl;

    return 0;

}