백준 1697 : 숨바꼭질

문제 링크입니다 https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

수빈이가 있는 위치로부터 동생의 위치까지 이동하는 방법이 모두 1초가 걸리므로, 각 위치를 정점으로 생각하고 1초가 걸려 이동할 수 있는 위치를 계속 큐에 넣고 빼서 확인하다가 최종 위치를 확인하면 최단 시간을 찾게 되는 BFS로 문제를 해결할 수 있었습니다. 자세한 설명은 주석을 참고해주세요!

 

 

[소스코드]

 

#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 100000 + 10;
 
int n, k, result[MAX];  // 이동한 시간을 저장할 result 배열
 
// 입력으로 주어진 n에서 bfs를 통해 이동 방법 3가지를 큐에 넣으면서
// 걸린 시간을 update 하다가 k를 만나면 그때까지의 시간을 반환하는 함수
int bfs(void) {
 
    bool check[MAX] = { 0, };  // 방문 처리를 해줄 check 배열
    queue <int> q;
 
    q.push(n);
    check[n] = true;
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        // 큐에서 꺼낸 값이 k와 같다면 현재까지 도달한 시간을 반환
        if (cur == k) return result[cur]; 
 
        // 두 배를 한 값이 범위안에 속하고 방문한적이 없으면
        if (cur * 2 < MAX && !check[cur * 2]) {
            q.push(cur * 2);
            check[cur * 2] = true;              // 위치 방문 표시
            result[cur * 2] = result[cur] + 1;  // 시간을 1초 증가시킴
        }
 
        // -1을 한 값이 범위안에 속하고 방문한적이 없으면
        if (cur - 1 >= 0 && !check[cur - 1]) {
            q.push(cur - 1);
            check[cur - 1] = true;
            result[cur - 1] = result[cur] + 1;
        }
 
        // +1을 한 값이 범위안에 속하고 방문한적이 없으면
        if (cur + 1 < MAX && !check[cur + 1]) {
            q.push(cur + 1);
            check[cur + 1] = true;
            result[cur + 1] = result[cur] + 1;
        }
    }
}
 
int main(void) {
    scanf("%d%d", &n, &k);
    printf("%d", bfs());
    return 0;
}