BOJ 1697 - 숨바꼭질

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

1697번: 숨바꼭질

 

 

BFS 를 이용해서 풀어야 하는 문제다.

 

이전 까지 내가 풀었던 BFS, DFS 문제들은

2차원 배열과 새 x,y 좌표를 위한 dx, dy 배열을 이용해 풀었다면

이 문제는 문제에서 제시된 세가지 식 (x + 1, x - 1, 2 * x) 를 이용해서 BFS 를 돌려야 했다.

그리고 시간에 대한 계산 부분은 큐를 한사이클 돌릴때마다 추가를 해줘야 했다

 

예를 들면 문제 예시에서 

N = 5, K = 17 일때, N 의 변화 양상을 보면

그림이 매우 불편..

대충 이런 모습으로 전개되는데

한 사이클은 그래프의 level 을 말하고

노드 5 에서 5 - 1, 5 + 1, 5 * 2 로 갈때 1초 그다음 9개 노드로 갈때 2초 이런식으로 증가된다.

 

또한 큐 사이즈 만큼 돌림으로써, 각 레벨에 대한 연산을 수행할 수 있게 된다.

 

- c++

#include <iostream>
#include <queue>
#define MAX 100001
 
using namespace std;
 
int N, K, cnt;
int checked[MAX];
 
void bfs(int num) {
    queue<int> q;
    q.push(num);
 
    while (!q.empty()) {
        int size = q.size();
 
        for (int i = 0; i < size; i++) {
            // 큐 사이즈 만큼 돌리는 이유는
            // 큐 내부의 값들에 대해서 +1, -1, *2 를 수행해야 하기 때문이다.
            int x = q.front();
            q.pop();
            if (x == K) {
                cout << cnt << '\n';
                return;
            }
            if (x > 0 && !checked[x - 1]) {
                checked[x - 1] = true;
                q.push(x - 1);
            }
            if (x < MAX - 1 && !checked[x + 1]) {
                checked[x + 1] = true;
                q.push(x + 1);
            }
            if (x * 2 < MAX && !checked[2 * x]) {
                checked[2 * x] = true;
                q.push(2 * x);
            }
        }
        cnt++;  // 큐 사이즈 만큼 한바퀴 돌면 다음 초로 넘어감.
    }
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N >> K;
 
    bfs(N);
 
    return 0;
}

 

 

 

처음엔 좌표 이동한다는 내용보고, 

DFS, BFS 관련된 그런 문제거니 했다가 

나중에 또 다시 생각해 보니

최소 시간에 이동해야 된다고 하니

동전 거스름돈 문제 처럼 그리디 인가 하면서

온갖 뻘짓하다가 다른사람들의 풀이를 보고 알게 되었다.

 

기본기가 많이 딸리는건가

 

- 참고

https://jun-itworld.tistory.com/19