[BOJ] 1697. 숨바꼭질

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

1697번: 숨바꼭질

수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이므로 bfs를 사용하면 된다.

수빈이가 갈 수 있는 모든 칸(정점)으로 1초마다 이동하고 방문한 칸은 가지 않는다.(최소 시간이 아니기 때문)

 

먼저 수빈이의 위치 n을 큐에 넣어주고 문제에 나온  x-1, x+1, 2*x 로 각각 이동해준다.(범위를 벗어나지 않는다면)

방문한 경우 visit배열에 걸린 시간을 저장해주고 큐에 넣어준다.

동생의 위치에 도착한 경우(visit[k]에 이동 시간이 저장되어 초기값 -1이 아닌 경우)에는 탐색을 종료해준다.

 

마지막으로 걸린 시간을 출력하면 끝.

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
 
 
 
int main() {
    int n, k;
    int visit[100001];
    memset(visit,-1,sizeof(visit));
    
    scanf("%d %d", &n, &k);
 
    queue<int> q;
 
 
    //수빈이의 위치
    q.push(n);
    visit[n] = 0;
 
 
    //bfs
    while(!q.empty()) {
        int x = q.front();
        q.pop();
 
 
        //x-1로 가는 경우
        //먼저 범위 체크후에 방문하지 않았으면 방문
        if(x-1 >= 0) {
            if(visit[x-1] == -1) {
                q.push(x-1);
                visit[x-1] = visit[x] + 1;
            }
        }
        
 
        //x+1로 가는 경우
        //먼저 범위 체크 후에 방문하지 않았으면 방문
        if(x+1 < 100001) {
            if(visit[x+1] == -1) {
                q.push(x+1);
                visit[x+1] = visit[x] + 1;
            }
        }
        
 
        //2*x로 가는 경우
        //먼저 범위 체크 후에 방문하지 않았으면 방문
        if(2*x < 100001) {
 
            if(visit[2*x] == -1) {
                q.push(2*x);
                visit[2*x] = visit[x] + 1;
            }
        }
        
 
        //동생의 위치에 도착했으면 더 탐색하지 않는다.
        if(visit[k] != -1) {
            break;
        }
 
    }
 
    
    printf("%d", visit[k]);
    return 0;
 
}