[BOJ] 1697 숨바꼭질

1. 문제링크

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

2. 해설

이 문제는 간단한 BFS문제이다.

1. n != k 이면 큐에 넣지 않는다.

2. n부터 BFS를 돌면서 k가 되는 순간 멈춘다.

3. 소스코드

#include <cstdio>
#include <queue>
using namespace std;

int check[100100];

bool checking(int next, int cur){
    if(next >= 0 && next <= 100000){
        if(check[next] == 0){
            return true;
        }
    }
    return false;
}

int main() {
    int n, k, ans=0;
    queue<int> q;
    scanf("%d %d", &n, &k);
    if(n != k){
        q.push(n);
    }
    while(!q.empty()){
        int cur = q.front(); q.pop();
        int next = cur + 1;
        if(checking(next, cur)){
            check[next] = check[cur] + 1;
            q.push(next);
        }
        if(next == k){
            ans = check[next];
            break;
        }
        next = cur - 1;
        if(checking(next, cur)){
            check[next] = check[cur] + 1;
            q.push(next);
        }
        if(next == k){
            ans = check[next];
            break;
        }
        next = cur * 2;
        if(checking(next, cur)){
            check[next] = check[cur] + 1;
            q.push(next);
        }
        if(next == k){
            ans = check[next];
            break;
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
}

4. 추가언급

이 문제에서 처음에 n과 k가 같은 지 확인을 하는데, 왜냐하면 n과 k가 같은 경우는 예를 들어 5라고 하면 check[6, 4, 10]이 1이 되고, check[5]는 6에서 넘어오게 되어 2가 적히게 된다. 그렇게 같을 때는 따로 확인을 해주어야 한다.