백준 13549 C++ 숨바꼭질 3 (BFS)

안녕하세요 여러분~~~~~~~

프루니입니다!!

 

오늘 풀어볼 문제는 백준 13549 숨바꼭질3 문제입니다~

언어는 C++입니다!

---

문제

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

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

---

입력

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

---

출력

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

---

문제 풀이

수빈이가 동생을 찾는데 걸리는 시간의 "최솟값"을 구해야하므로 BFS를 사용해요!

BFS를 돌리면서 해야하는 연산은 총 3개에요!

바로 수빈이의 현재 위치에서 1을 빼거나 1을 더하거나 2를 곱하는것이에요~

 

그래서 할 일을 정리해보면!

1. 수빈이의 현재 위치를 변수로 하나 선언하기

2. 현재위치 * 2, 현재위치 - 1, 현재위치 + 1 -->이렇게 3가지 연산을 각각 수행한 결과들을 큐에 추가하기

2. 큐에서 현재 검사하는 값이 동생의 위치가 일치하면 바로 해당 배열의 값(시간의 최솟값)을 리턴하기

 

자 그런데 중요한것이 있어요

바로 2번에서 빨간색으로 표시한 부분인데요! 연산을 할때 현재위치*2하는 연산을 먼저 해야한답니다!

그 이유는 "1"이라는 숫자때문인데요~

1은 더하기1을 한 결과와 곱하기 2를 한 결과가 모두 2로 같아요!!

현재 문제에서는 더하기나 빼기 연산에 대해서는 1초라는 시간이 소요되고 곱하기 연산에 대해서는 0초가 소요됩니다.

또한 시간의 최솟값을 구해야하기때문에 같은 결과에 대해서는 시간이 덜 걸리는 연산을 선택해야해요!

BFS를 돌릴때 흔히 visited라는 배열을 이용해서 이미 방문한 경로는 다시 검사하지 않아요~

따라서 만약 현재 값이 1일때 더하기 연산이 먼저 이루어진다면 2라는 값에 대해서는 1초가 소요된다고 입력되고 그 뒤 연산들이 이루어지지 않을거에요

그러므로 곱하기연산을 먼저 해줘야 한답니다!!!!

 

자 그럼 코드로 구현해볼게요~

 

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

int visited[100001];

int BFS(int start, int end)
{
    queue<int> q;
    q.push(start);
    visited[start] = 1;

    while (!q.empty())
    {
        int front = q.front();
        q.pop();

        if (front == end)
        {
            return visited[front];
        }

        int go[3] = { front * 2, front - 1, front + 1 };
        
        for (int i = 0; i < 3; ++i)
        {
            int next = go[i];
            if (next < 0 || next > 100000)
            {
                continue;
            }

            if (!visited[next] || visited[next] > visited[front] + 1)
            {
                if (i == 0)
                {
                    visited[next] = visited[front];
                }
                else
                {
                    visited[next] = visited[front] + 1;
                }
                q.push(next);
            }
        }
    }
    
}

int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);

    int N, K;
    cin >> N >> K;

    int res = BFS(N, K);
    cout << --res << '\n';

    return 0;
}

 

 

여러분~ 모두 고생하셨습니다!!

도움이 되셨다면 공감버튼 한번씩 눌러주시고 또 방문해주세요~

질문사항이나 잘못된 점은 댓글로 달아주시면 바로!! 달려가겠습니다!

알고리즘 마스터 선생님들 도와주세요!!!

알고리즘 마스터 가주아~~~~~~~~~~~~~~~~~~~~~~~~~~~!!!

 

그럼 저는 다음 문제를 가지고 또 돌아올게요~

안녕~~~~~~~