[BFS] 13529번 숨바꼭질3

13549번 숨바꼭질 3

 

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

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

5 17

 

예제 출력

2

 

해결방법

숨바꼭질 의 변형 문제로 최소 시간을 구하는 문제이다

 

 

⭐️ 솔루션 ⭐️

최소 시간을 찾아야하기 때문에 목표 노드에 도달했을 때 최소 시간을 계속 갱신한다

 

• 목표노드 도달 시, 최소 시간을 갱신한다
• 최소 시간 보다 큰 경우는 제외한다

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

if(ans < cnt) continue;

visited[now] = true;

if(now == m){
    ans = min(ans,cnt);
    continue;
}

 

 

 

소스코드

#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,ans;
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(ans < cnt) continue;
        
        visited[now] = true;
        
        if(now == m){
            ans = min(ans,cnt);
            continue;
        }
        
        // 앞으로 한칸 가는 경우
        if(now+1 <= m && !visited[now+1]){
            q.push(node(now+1,cnt+1));
        }
        
        // 뒤로 한칸 가는 경우
        if(now-1 >= 0 && !visited[now-1]){
            q.push(node(now-1,cnt+1));
        }
        
        // 순간이동 하는 경우
        if(now*2 < 2*m && !visited[now*2]){
            q.push(node(now*2,cnt));
        }
    }
}

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));
    
    ans = INF;
    bfs();
    cout << ans << "\n";
    
    return 0;
}