[백준 1697번] - 숨바꼭질

1697번: 숨바꼭질

[문제 설명]

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	160488	45718	28693	25.059%

문제

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

---

[문제 풀이]

아 정말 오래걸렸다..

30분~1시간 정도 풀다가 안되면 멈췄어야 했다.

거의 다 풀린거같아서 잡고 있다보니 시간을 많이 써버렸다..

 

문제 접근 방식은 최단 시간을 구하는것으로 BFS를 사용하면 될거라고 생각했다.

이동 할 수 있는 방법은 {now-1, now+1, now*2} 3가지이다.

우선 간단한 부분은 수빈이가 있는 위치가 동생보다 크다면 (수빈이 위치 - 동생 위치)가 정답이 된다.

뒤로 돌아 갈 수 있는 방법은 now-1을 반복하는것 외에는 없다.

 

pair<현재 위치,걸린 시간>를 사용하여 문제를 풀었다.

문제를 다 풀고 나서 든 생각이지만 두번째 걸린시간이 굳이 필요했을까 싶다.

 

아무튼,  BFS를 탐색하는 것 처럼 queue가 다 빌때까지 반복문을 돌면서

queue에서 하나씩 빼서 값을 비교한다.

이동 할 수 있는 방법 3가지를 {now-1, now+1, now*2}  queue에 모두 넣어준다.

 

이 문제의 핵심이 바로 위 3가지를 queue에 넣을 조건을 결정하는것 같다.

3가지 모두 방문하지 않았을 경우에만 큐에 넣어준다.

각각의 조건은

now-1의 조건은 우리가 탐색하는 범위 0보다 크거나 같을 조건에서만 큐에 넣어준다.

now+1의 조건 또한 우리가 탐색하는 범위 안에서만 큐에 넣어준다.

now*2의 조건은 기본적으로는 동일하게 넣어주지만,

만약 넣으려는 값이 동생 위치보다 클 경우에는 현재까지 탐색한 시간 + 두 위치의 차이 만큼 더해주면 걸린 탐색 시간이 된다.

 

풀고나면 별 조건 아닌거 같지만, 풀면서 봤을때는 정말 헷갈렸다.

조건을 경우에 맞게 다 넣은거 같았지만, 조건문의 순서에 따라 문제의 답이 달라졌다.

확실하게 모든 경우를 생각하고 코드를 작성하는 습관을 들여야겠다고 생각했다.

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

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

using namespace std;

#define MAX 100001
vector<int> v;

void bfs(int start, int target)
{
    queue<pair<int, int>> q;
    q.push({ start,0 });

    while (!q.empty())
    {
        int first = q.front().first;
        int second = q.front().second;
        if (first == target)
        {
            cout << second << "\n";
            break;
        }
        q.pop();
        
        if (first - 1 >= 0 && v[first - 1] == 0)
        {
            v[first - 1] = second + 1;
            q.push({ first - 1,second + 1 });
        }
        if(first + 1 < MAX && v[first + 1] == 0)
        {
            v[first + 1] = second + 1;
            q.push({ first + 1,second + 1 });
        }
        if(first * 2 > 0 && first * 2 < MAX && v[first * 2] == 0)
        {
            int tmp = 0;
            if (first * 2 > target)
            {
                tmp = first * 2 - target + second;
            }
            else tmp = second + 1;
            v[first * 2] = tmp;
            q.push({ first * 2,second + 1 });
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    int n, k;

    cin >> n >> k;
    if (n >= k)
    {
        cout << n - k << "\n";
        return 0;
    }
    v = move(vector<int>(MAX, 0));
    bfs(n, k);

    return 0;
}