Baekjoon/C

[백준] 1697번 숨바꼭질

달의요정루나 2022. 7. 19. 21:40

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

#include <stdio.h>

int n,k;
int num[100005]={0,};
int queue[100005]={0,};

int BFS(int pos);

int main()
{
    scanf("%d %d",&n,&k);
    printf("%d",BFS(n));
}

int BFS(int pos){
    int front = 0, rear=1,pop;
    queue[front]=pos;
    while(front < rear){
        pop = queue[front++];
        if(pop+1<=100000 && !num[pop+1] && pos!=pop+1){
            num[pop+1]=num[pop]+1;
            queue[rear++]=pop+1;
            if(pop+1 == k){
                break;
            }
        }
        if(pop-1>=0 && !num[pop-1] && pos!=pop-1){
            num[pop-1]=num[pop]+1;
            queue[rear++]=pop-1;
            if(pop-1 == k){
                break;
            }
        }
        if(pop*2<=100000 && !num[pop*2] && pos!=pop*2){
            num[pop*2]=num[pop]+1;
            queue[rear++]=pop*2;
            if(pop*2 == k){
                break;
            }
        }
        
    }
    return num[k];
}