[백준알고리즘] 1967번 숨바꼭질

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

• 1697번
• 제출
• 맞은 사람
• 숏코딩
• 풀이
• 풀이 작성
• 풀이 요청
• 재채점/수정
• 채점 현황
• 내 소스
• 강의
• 질문 검색

숨바꼭질 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	43205	11848	7359	24.651%

문제

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

dfs로 했다가 시간 초과나서 bfs로 풀어야 한다는 것을 계속 고친지 1시간만에 깨달음... 바보 멍청한 자식....

이따가 다시 bfs로 짜보아야 겠다...

<dfs로 짜서 실패했던 코드>

#include<iostream>
using namespace std;
 
int N, K;
int min_value = 10000;
bool visited[100001];
 
void dfs(int _N, int value)
{
    visited[_N] = true;
 
    if (_N == K) {
        if (min_value > value) min_value = value;
        return;
    }
 
    if (min_value > value + 1)
    {
        if (!visited[_N - 1] && _N - 1 >= 0 && _N - 1 <= 100000)
        {
            dfs(_N - 1, value + 1);
            visited[_N - 1] = false;
        }
        if (!visited[_N + 1] && _N + 1 >= 0 && _N + 1 <= 100000)
        {
            dfs(_N + 1, value + 1);
            visited[_N + 1] = false;
        }
        if (!visited[2 * _N] && 2 * _N >= 0 && 2 * _N <= 100000)
        {
            dfs(2 * _N, value + 1);
            visited[2 * _N] = false;
        }
    }
    return;
}
 
 
int main(void)
{
    cin >> N >> K;
 
    if (N > K) cout << N - K;
    else if (N == K)  cout << 0;
    else
    {
        dfs(N, 0);
        cout << min_value;
    }
    
    return 0;
}

<bfs로 고쳐 성공한 코드>

#include<iostream>
#include<queue>
using namespace std;
 
int main(void)
{
    int N, K = 0;
    int value = 0;
    bool visited[100001] = {false};
    queue<int> q;
 
    cin >> N >> K;
 
    if (N > K) cout << N - K;
    else if (N == K)  cout << 0;
    else
    {
        q.push(N);
        visited[N] = true;
 
        while (!q.empty())
        {
            int qsize = q.size();
 
            while (qsize--)
            {
                int index = q.front();
                q.pop();
 
                if (index == K) {
                    cout << value;
                    return 0;
                }
 
                if (!visited[index + 1] && index + 1 >= 0 && index + 1 <= 100000)
                {
                    q.push(index + 1);
                    visited[index + 1] = true;
                }
                if (!visited[index - 1] && index - 1 >= 0 && index - 1 <= 100000)
                {
                    q.push(index - 1);
                    visited[index - 1] = true;
                }
                if (!visited[2 * index] && 2*index >= 0 && 2*index <= 100000)
                {
                    q.push(2 * index);
                    visited[2 * index] = true;
                }
            }
            value++;
        }
    }
    return 0;
}