[BOJ] #1697 숨바꼭질

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

1697번: 숨바꼭질

---

"가장 빠른 시간"을 구해야 하는 문제니 BFS를 적용하여 풀었다. 처음엔 그냥 산술적으로 브루트포스 같은것들을 적용시켜 도전하려 했으나, 주어지는 입력의 최댓값이 100,000이고, 제한시간이 2초니까 O(N^2)짜리 코드로 풀면 시간초과가 날것이다. 따라서, BFS를 이용하여 푸는쪽으로 방향을 잡았다.

그래프를 형태가 인접리스트로 주어지는것이 아니기 때문에 오로지 큐 자료구조만 이용하여 BFS를 돌려야 한다. 그에 맞춰 기존에 알고있었던 BFS 알고리즘 코드를 살짝 바꾸어 풀었다. 또한, 최단 시간을 나타내는 cnt 변수를 큐 자료구조의 구성원으로서 처리하여 각각의 연산마다 다른 cnt값을 가지도록 구현하였다.

BFS 문제를 몇개 풀다보니 조금 감이 잡히는것 같긴 한데, 그래도 아직 부족한것 같다. 실버는 그래도 어찌어찌 푸는데 아마 골드티어 문제들 부터는 어려워지는 느낌? 많이 풀면서 감을 익혀야 할듯 하다.

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100005

bool visited[MAX];
queue<pair<int,int>> Q;
int N,K;

int F(int a, int c) {
    visited[a] = true;
    Q.push(make_pair(a,c));
    
    while(!Q.empty()) {
        int n = Q.front().first;
        int cnt = Q.front().second;
        Q.pop();

        if (n == K) return cnt;

        if (n+1>=0 && n+1<MAX && !visited[n+1]) {
            visited[n] = true;
            Q.push(make_pair(n+1, cnt+1));
        }
        if (n-1>=0 && n-1<MAX && !visited[n-1]) {
            visited[n] = true;
            Q.push(make_pair(n-1, cnt+1));
        }
        if (n*2>=0 && n*2<MAX && !visited[n*2]) {
            visited[n*2] = true;
            Q.push(make_pair(n*2, cnt+1));
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> K;

    cout << F(N,0) << '\n';

    return 0;
}