[백준 1697] 숨바꼭질(C++)

📕문제

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

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

---

📕입력

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

---

📕출력

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

---

💡문제 해석

문제를 보면 갈 수 있는 "최소"의 시간을 요구하고 있다.

이 말은 즉 BFS를 사용해서 풀어!라는 뜻이라고 생각했다.

이 문제의 관건은 시간을 어떻게 하면 더 절약할 수 있는가에 달려있다.

나도 처음에 그냥 머리부터 박았다가 값이 작은 input일 때는 가능했지만 값이 커지니 컴퓨터가 작동을 안 하는 현상이 발생했다. 실제로 0~100000까지의 범위라서 예외처리를 해주지 않는다면 엄청난 시간이 발생할 것이다.

 

📜코드

/*
실버1 백준 1697 숨박꼭질
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
void bfs();
long long int n, k;
queue<long long int> q;
vector<vector<int>> graph;
int step = 1;
vector<int> a, b, c;
vector<int>visit;
int main()
{
    cin >> n >> k;
    visit.resize(100000);
    if (n == k)
    {
        cout << 0;
        return 0;
    }
    bfs();
}
void bfs()
{
    //처음으로 queue에 k가 들어가는 시간을 찾아보자.
    q.push(n);
    int size = q.size();
    int Size = 0;
    while (!q.empty())
    {
        int answer = q.front();
        q.pop();
        Size++;
        if (answer - 1 >= 0 && visit[answer-1]==0)
        {
            q.push(answer - 1);
            visit[answer-1]=1;
        }
        if (answer + 1 <= 100000&&visit[answer+1]==0)
        {
            q.push(answer + 1);
            visit[answer+1]=1;
        }
        if (answer * 2 <= 100000&&visit[answer*2]==0)
        {
            q.push(answer * 2);
            visit[answer*2]=1;
        }
        if (answer - 1 == k || answer + 1 == k || answer * 2 == k)
        {
            cout << step;
            break;
        }
        if (size == Size)
        {
            step++;
            size = q.size();
            Size = 0;
        }
    }
}

 

💡코드 설명

• n과 k를 입력받고 만약 n과 k가 같다면 함수를 실행시키지 않고 바로 0을 출력하고 종료한다.
• 다를 경우에는 BFS함수를 실행시킨다.
• size와 Size라는 변수를 만든다. 이는 몇 초가 흘렀는지를 계산하기 위한 변수이다.
• 하나의 수로 3개의 다른 수가 파생된다. 그것을 하나하나 큐에 넣어준다.
• 여기서 만약 그 수가 100000을 넘거나, 이미 한번 탐색했던 수라면 넣어주지 않는다.
• 만약 3개의 다른 수 중에서 내가 찾고자 하는 k값과 같은 수가 있다면 그 즉시 함수를 종료시키고 그때의 시간을 출력한다.

 

✔느낀 점

• 시간을 어떻게 하면 빠르게 줄일 수 있을까에 대한 생각보단 시간 초과 때문에 틀렸다는 사실을 인지하는 것이 중요한 것 같다.
• 실제로 온라인 저지에서  틀렸는데 시간 초과라고 뜨지 않고, 그냥 틀렸습니다라고 결과가 출력돼서 엉뚱한 방향으로 갔다.