백준[1697] - 숨바꼭질

문제

백준 1697 문제 보기

접근 방법

숨박꼭질 문제는 좌표 값이 10만까지 있어 이를 dfs를 활용해 문제를 풀 경우 시간초과가 날수 있다. 따라서 최소값을 구하는데 편리한 bfs를 활용하면 문제를 쉽게 풀 수 있다.

• -1을 한 경우.
• +1을 한 경우.
• *2를 한 경우.

다음과 같이 모든 경우를 나누어 큐에 넣어주면 된다.

코드

#include <iostream>
#include <queue>
#include <cstring>
#include <utility>

using namespace std;

int N, K;
int dp[100001];

queue<pair<int, int>> q;
bool visited[100001];

int main() {

    cin >> N >> K;

    memset(dp, 0, sizeof(dp));
    memset(visited, 0, sizeof(visited));

    q.push(make_pair(N, 0));

    while (!q.empty()) {
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if (cur < 0 || cur > 100000) continue;
        if (visited[cur]) continue;

        visited[cur] = true;

        if (cur == K){
            cout << cnt;
            return 0;
        }

        q.push({ cur * 2, cnt + 1 });
        q.push({ cur + 1, cnt + 1 });
        q.push({ cur - 1, cnt + 1 });
    }
    return 0;
}