[백준][C++] 1697: 숨바꼭질

 

 

 

 

 

 

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

1697번: 숨바꼭질

 

 

 

 

 

---

- 문제

 

N(0 <= N <= 100,000)에서 점 K(0 <= K <= 100,000)로 가는 방법이 N-1, N+1, N*2 이렇게 3가지 방법이 있을 때 N 에서 K로 가는 가장 빠른 시간을 구하는 문제다.

 

 

---

- 해설

 

dfs와 bfs 중에서 bfs가 가장 빠른 시간을 구하는 문제이므로, bfs로 풀면 될 것 같다.

 

 

아래 풀이에서는 queue가 빌때까지 반복하므로 시간이 오래 걸릴수도 있는데, 제출해본 결과 시간초과는 안 떠서 그대로 유지했지만, 시간초과가 떴으면, K에 도달하면 break하게 만들었을 것 같다.

 

 

 

---

- 풀이

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int N, K;
    queue<pair<int, int>> q;
    int spot[100001] = {0};
    bool visited[100001] = {false};
    int result[100001] = {0};
    cin >> N >> K;

    q.push(pair<int, int>(N, 0));
    while (!q.empty())
    {
        int now = q.front().first, cnt = q.front().second;
        q.pop();
        if (!visited[now] && (now >= 0 && now < 100001))
        {
            visited[now] = true;
            if (result[now] == 0)
            {
                result[now] = cnt;
            }
            cnt++;
            q.push(pair<int, int>(now - 1, cnt));
            q.push(pair<int, int>(now + 1, cnt));
            q.push(pair<int, int>(now * 2, cnt));
        }
    }

    cout << result[K];

    return 0;
}

 

 

---

- 새롭게 알게 된 점