백준 12851번: 숨바꼭질2 (C++)

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

특정 위치까지 이동할 때 최소 비용을 구해주고, 최소 비용으로 그 위치까지 도달하는 방법의 수를 구해주면 된다.

처음에는 목적지만 중복해서 방문할 수 있도록 해주면 된다고 생각했는데, 이렇게 접근하게 되면

1 -> 2로 가는경우 1+1 로 2로 가는 경우와, 1 * 2로 2로 가는 경우를 모두 잡아낼 수 있지만,

1 -> 4로 가는 경우를 생각해보면 1+1 -> 2, 2 *2 - > 4 로 가는 경우에서 2를 방문 처리한 이후에 재방문을 허용하지 않기 때문에 문제가 된다.

따라서 재방문을 목적지가 아니더라도 허용해주어야 하는데, 당연히 모든 경우에 허용해주면 안되고, 이전에 방문했을 때의 비용과 같은 경우에만 허용해주면 된다.

당연하게도 이전에 방문했던 비용보다 작은 비용으로 재방문하는 경우는 나오지 않는다.

즉, 목적지가 아닌 지점을 재방문 할 때에는, 이미 설정되어 있는 그 지점으로 이동하는 비용과, 현재 지점 + 1 을 비교해서, 같은 경우에는 재방문을 허용한다(큐에 삽입).

목적지인 지점을 재방문 할 경우에는, 위와 같이 비용 비교를 해주고, 동일 비용으로 재방문하는 경우 카운트를 1 증가시켜준다.

목적지를 거쳐서 가는 다른 지점은 방문할 필요가 없기 때문에 큐에 삽입은 하지 않는다.

#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
int m[100001], src, dst, dis[100001];
const int d[3] = { 0,1,2 };
queue<int> q;
int cnt = 1; //무조건 한 가지 방법은 나온다
void bfs() {
    q.push(src);
    dis[src]++;
    while (!q.empty()) {
        int qs = q.size();
        for (int t = 0; t < qs; t++) {
            int cur = q.front();
            q.pop();
            
            int np;
            for (int i = 0; i < 3; i++) {
                if (d[i] == 0)
                    np = cur + 1;
                else if (d[i] == 1)
                    np = cur - 1;
                else
                    np = cur * 2;
                if (np < 0 || np > 100000) continue; 
                
                //이전에 방문한 적이 있더라도, 동일 비용으로 방문이 가능한 경우
                if (dis[cur] + 1 == dis[np] && dis[np] >= 0){ 
                    if (np == dst) { //목적지인 경우, 그 이후를 탐색할 필요가 없으므로 push 하지 않음
                        cnt++;
                        continue;
                    }
                    else { //이전에 방문한 곳을 여러 방법으로 거쳐갈 수 있으므로 push
                        q.push(np);
                        continue;
                    }
                    
                    //_sleep(500);
                }
 
                //위의 경우를 제외하고 비용이 양수인 경우는, 최소 비용으로 방문하는 경우가 아님
                if (dis[np] >= 0) continue; 
 
                //방문하지 않은 곳을 방문해줌
                dis[np] = dis[cur] + 1;
                q.push(np);
            }
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    
    cout << dis[dst] << '\n' << cnt;
    
    return 0;
}