[백준] 12851번: 숨바꼭질 2

Kim Yuhyeon·2023년 8월 17일

알고리즘

알고리즘 + 자료구조

목록 보기

128/161

문제

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

접근 방법

1. 완전 탐색

동생보다 왼쪽에 있으면 +1, *2
동생보다 오른쪽에 있으면 -1
재귀함수를 돌려서 완전 탐색으로 시도해보았으나,

시간복잡도가 초과되었고, 로직도 잘못되었음
5 -> 4 -> 8 -> 16 -> 17 로 갈 수도 있는데
뺄샘을 동생보다 오른쪽에 있을 때만 해서 fail

2. BFS

방문 하지 않았을 때 큐에 넣고 탐색을 돌린다.
방문을 했지만 현재 방문 시간 + 1이 다음 방문 시간과 같다면 방문 횟수를 누적시킨다.

풀이

1. 완전탐색

#include <iostream>

#define INF 987654321
#define MAX 100000
using namespace std;

int N, K;

int dp[MAX+4]; // 도달하는 최소 시간을 담은 배열
int cnt[MAX+4]; // 도달하는 최소 시간의 갯수 담은 배열

void FastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void Init()
{
    for(int i=0; i<=MAX; i++)
        dp[i] = INF;
}

void Input()
{
    cin >> N >> K;
}

void Recursive(int time, int num)
{   
    // 이미 최소 시간보다 오래 걸렸다면 찾지 않음. 
    if (time > dp[num])
        return;


    // num에 도착하는 최소 시간 갱신
    else if (time < dp[num])
    {
        dp[num] = time;
        cnt[num] = 1;
    }
    else if (time == dp[num])
    {
        cnt[num]++;
    }


    // 동생을 찾았다 
    if (num == K)
        return; 
    
    // 동생보다 많이 갔을 때만 빼기
    else if (num > K)
    {   
        if (num-1 >= 0)
           Recursive(time+1, num-1);
    }
    else // 동생보다 작을 때는 더하거나 곱하기 
    {
        if (num+1 <= MAX)
            Recursive(time+1, num+1);
        
        if (num*2 <= MAX)
            Recursive(time+1, num*2);
    }
    
}


void Solve()
{

    Init();
    // 횟수, 숫자 

    // K가 더 작으면 -1로 갈 수밖에 없음, 같으면 0
    if (K <= N) cout << N - K << '\n' << 1;
    else 
    {
        Recursive(-1, N);
        cout << dp[K] << '\n' << cnt[K];
    }
   
}

int main()
{
    FastIO();
    Input();
    Solve();

    return 0;
}

결과

시간 초과

2. BFS

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

#define INF 987654321
#define MAX 100000
using namespace std;

int N, K;

int cnt[MAX+4]; // 도달 횟수
int visited[MAX+4]; // 도달하는 시간

void FastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void Input()
{
    cin >> N >> K;
}


void Solve()
{    

    // 같은 경우 
    if (N == K)
        cout << "0\n1";
    else 
    {
        queue<int> q;
    
        q.push(N); 
        visited[N] = 1;
        cnt[N] = 1;

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

            if (curr == K)
                break;
        
            for(int next : {curr-1, curr+1, curr*2})
            {
                // 범위 안에 있을 때만
                if (0 <= next && next <= MAX)
                {
                    // 방문하지 않았을 때
                    if (!visited[next])
                    {
                        q.push(next);        
                        cnt[next] += cnt[curr];
                        visited[next] = visited[curr] + 1;
                    }
                    // 
                    else if (visited[next] == visited[curr] + 1)  
                    {
                        cnt[next] += cnt[curr];
                    }
                }
            }
        }
        

        cout << visited[K] - 1 << '\n' << cnt[K];

    }
   

}

int main()
{
    FastIO();
    Input();
    Solve();

    return 0;
}