숨바꼭질 2

문제 분석 및 풀이

설계 분석

• BFS를 사용하는 문제.
• 처음에는 그리디로 접근 했다가, +1 -1 둘 다 있어서 안된다는 것을 알았다.
• BFS를 통해서 최소 거리를 찾고, 최소 거리를 가지는 경로의 수를 찾는다.
• $O(3N) = O(N)$에 가능

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N,K;
const int MAX = 100001;
int ans;
vector<int> visited(MAX, MAX);

bool CanGo(int x, int cnt)
{
    // 경계확인
    if (x < 0 || x >= MAX) return false;
    // 최소경로로 방문한 적 있는지 확인
    if (visited[x] < cnt) return false;

    return true;
}

void BFS(int x)
{
    int dx[3] = {-1, 1, 2};
    queue<pair<int,int>> q;
    q.push({x,0});
    visited[x] = 0;

    while(!q.empty())
    {
        int pos = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        // 현재 위치가 K이고 cnt가 최솟값이면 경로 수 증가
        if (cnt == visited[K] && pos == K) ans++; 
        int nx = 0;
        for (int i=0; i<3; i++)
        {
            // *2
            if (i == 2)
            {
                nx = pos * 2;
            }
            // +1, -1
            else
            {
                nx = pos + dx[i];
            }
            
            if (CanGo(nx, cnt+1))
            {
                visited[nx] = cnt+1;
                q.push({nx, cnt+1});
            }
        }
    }
}

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

    cin >> N >> K;
    
    BFS(N);

    // K까지의 거리의 최소거리
    cout << visited[K] << "\n";
    // 최소경로의 개수
    cout << ans << "\n";

    return 0;
}