[BFS] 12851번 숨바꼭질2

12851번 숨바꼭질 2

 

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

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

예제 입력

5 17

 

예제 출력

4
2

 

해결방법

숨바꼭질 의 변형 문제로 최단거리와 최단거리를 갖는 경우의 수를 구하는 문제이다

중복처리 부분이 조금 어려웠다..

 

 

⭐️ 솔루션 ⭐️

목표 노드에 도달했을 경우의 거리를 저장해놓은 뒤, 그 거리보다 크다면 제외하는 로직을 구현했다

 

예제의 TC 는 n이 5 , k가 17 이다

최단 경로는 4이며 4의 거리를 갖는 경로는 아래와 같다

5 → 10 → 9 → 18 → 17
5 → 4 → 8 → 16 → 17

 

다른 노드들은 중복 처리를 해도 상관없지만 위에서 보듯이 17 은 몇번이고 탐색이 가능해야 한다

따라서 visited 배열을 통해 방문처리를 하는 위치를 변경해야 했다

 

변경 전 에는 다음 노드를 확인하면서 큐에 넣을 때 방문 처리를 해줬다

// 앞으로 한칸 가는 경우
if(now+1 <= m && !visited[now+1]){
    q.push(node(now+1,cnt+1));
    
    if(now+1 != m) visited[now+1] = true;
}

 

변경 후 에는 큐에서 꺼낸 후 방문 처리를 해줬다

int now = q.front().now;
int cnt = q.front().cnt;
q.pop();

if(ans1 < cnt) continue;

visited[now] = true;

…

 

이는 무슨 차이일까??

위의 경로를 보며 이해를 해야한다

5에서 출발해 쭉쭉 진행 되다가 큐에는 같은 거리를 가지고 있는 18 16 이 동시에 있을 것이다

만약 변경 전처럼 큐에 넣을 때 방문 처리를 한다면 애초에 16 은 큐에 들어가지 못했을 것이다

이미 18 을 넣으며 방문처리를 완료했기 때문이다

하지만 방문 처리를 큐에서 뺄 때 한다면 큐에는 같은 거리를 가지고 있는 노드들이 동시에 존재할 것 이고 정답의 경우를 모두 확인 할 수 있을 것이다 !!

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 200001
#define INF 987654321
using namespace std;

struct node {
    int now,cnt;
    
    node() { }
    node(int n,int c) : now(n),cnt(c) { }
};

int n,m,ans1,ans2;
bool visited[MAX];

void bfs(){
    queue<node> q;
    q.push(node(n,0));
    
    while(!q.empty()){
        int now = q.front().now;
        int cnt = q.front().cnt;
        q.pop();
        
        if(ans1 < cnt) continue;
        
        visited[now] = true;
        
        if(now == m){
            ans1 = min(ans1,cnt);
            ans2++;
            continue;
        }
        
        // 앞으로 한칸 가는 경우
        if(now+1 <= m && !visited[now+1]){
            q.push(node(now+1,cnt+1));
            
//            if(now+1 != m) visited[now+1] = true;
        }
        
        // 뒤로 한칸 가는 경우
        if(now-1 >= 0 && !visited[now-1]){
            q.push(node(now-1,cnt+1));
            
//            if(now-1 != m) visited[now-1] = true;
        }
        
        // 순간이동 하는 경우
        if(now*2 < 2*m && !visited[now*2]){
            q.push(node(now*2,cnt+1));
            
//            if(now*2 != m) visited[now*2] = true;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    memset(visited, false, sizeof(visited));
    ans1 = INF;
    ans2 = 0;
    
    bfs();
    
    cout << ans1 << "\n";
    cout << ans2 << "\n";
    
    return 0;
}