이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 50 번째 글 입니다.
목차
실버2 : 그래프 문제이다.
이 문제의 핵심은, 해당 위치에서 3가지의 선택을 할 수 있다는 점이다. 이 3가지의 선택 각각에 해당하는 위치에서 또 3가지의 선택을 할 수 있다. 그 선택을 연이어한 결과 문제의 답이 있다.
하지만 이 문제는 DFS로 접근할 수 없는데, 그 이유는, 각각의 선택을 깊이 기준으로 탐색했을 때, 답에 다다르지 못하는 상황이 있을 수 있기 때문이다. 따라서 무한 루프에 빠지거나, 혹은 이 부분을 거르는 코드를 작성해야 하는데 상당히 번거롭다.
이런 경우 오히려 BFS로 생각했을 때, 문제가 확 와닿는 경우가 많다. BFS로 탐색할 경우, 시간의 기준으로 완전 탐색하기 때문에 이 문제의 의도와 정확히 맞아 떨어진다. 최대한 짧은 시간에 답과 일치할 경우 반복문을 빠져나오면 되기 때문이다. 따라서 위치에 따른 시간을 저장할 필요가 있다.
이 때, 선택지에 $+1, -1$이 있고 중간중간 $\times2$ 도 있어 중복되는 위치에 방문할 가능성이 있다. 이 부분의 시간 복잡도를 줄이기 위해 메모리를 사용하여 코드를 짰다.
Code
// 실버1 : 백준 1697번 숨바꼭질
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N = 0, K = 0;
bool map[100001] = {0};
int main(){
cin >> N >> K;
queue<pair<int, int>> q;
int ans = 0;
q.push(make_pair(N, 0));
while (!q.empty()) {
int now = q.front().first, time = q.front().second;
q.pop();
if (map[now] == true) continue;
map[now] = true;
if (now == K) {
ans = time; break;
}
if (now-1 >= 0) q.push(make_pair(now-1, time+1));
if (now+1 <= 100000) q.push(make_pair(now+1, time+1));
if (now*2 <= 100000) q.push(make_pair(now*2, time+1));
}
cout << ans << '\n';
}