백준 - 1697 숨바꼭질

문제 링크

BFS 문제다. 값의 범위만 조심하면 어려울 것 없는 문제였다.

다만 지금까지 풀었던 BFS는 방문을 체크하는 변수와 현재 탐색 레벨의 변수를 따로 두고 풀었는데, 이번에는 이전 문제와는 다르게,방문을 체크하는 변수 안에 현재 탐색 레벨을 담았다. 다만 그 체크를 위해 맨 처음 값이 1로 시작해야 했기에, 마지막 결과 값에서 1을 빼서 반환했다.

밑은 내가 풀이한 코드이다. 

#include <cstdio>
#include <queue>
using namespace std;
//기존에 풀었던 BFS문제와는 다르게, visited 배열에 현재 레벨도 저장하였다. 
int n, k, visited[100001]={0,};
queue<int> q;
int bfs(){
    //큐에 수빈의 위치를 넣고, 방문을 체크하는 배열에 1을 넣어준다. 
    q.push(n); visited[n] = 1;
    //bfs 시작 
    while(!q.empty()){
        //큐를 꺼내고, 수빈이가 동생의 위치에 도달했는지 확인한다. 
        int p = q.front(); q.pop();
        if(p==k) return visited[p]-1;
        
        //수빈이 현재 위치 -1이 0보다 크거나 같고, 방문한 적이 없을경우. 현재 값에서 레벨을 1증가시켜 큐에 넣어준다. 
        if(p-1>=0&&visited[p-1]==0){
            visited[p-1] = visited[p]+1;
            q.push(p-1);
        }
        //수빈이 현재 위치의 +1이 100,000보다 작거나 같고, 방문한 적이 없을경우.
        if(p+1<=100000&&visited[p+1]==0){
            visited[p+1] = visited[p]+1;
            q.push(p+1);
        }
        //수빈이 현재 위치의 2배가 0보다 크거나 같고, 방문한 적이 없을경우.
        if(2*p<=100000&&visited[2*p]==0){
            visited[2*p] = visited[p]+1;
            q.push(2*p);
        }
    }
}
int main(){
    scanf("%d %d",&n,&k);
    printf("%d",bfs());
}