BOJ - 숨바꼭질(1697)

풀이1

실버1 : BFS 문제이다.

Code

from collections import deque
import sys
 
 
input = sys.stdin.readline
 
MAXNUM = 1e6
N, K = map(int, input().split())
visited = [False] * int(MAXNUM + 1)
 
 
def BFS():
    q = deque()
    q.append((N, 0))  # position, cost
 
    while q:
        pos, cost = q.popleft()
        visited[pos] = True
 
        if pos == K:
            return cost
 
        nexts = [(pos - 1, cost + 1), (pos + 1, cost + 1), (2 * pos, cost + 1)]
 
        for npos, ncost in nexts:
            if 0 <= npos <= MAXNUM and visited[npos] == False:
                q.append((npos, ncost))
 
 
ans = BFS()
print(ans)
 

풀이2

실버2 : 그래프 문제이다.

이 문제의 핵심은, 해당 위치에서 3가지의 선택을 할 수 있다는 점이다. 이 3가지의 선택 각각에 해당하는 위치에서 또 3가지의 선택을 할 수 있다. 그 선택을 연이어한 결과 문제의 답이 있다.

하지만 이 문제는 DFS로 접근할 수 없는데, 그 이유는, 각각의 선택을 깊이 기준으로 탐색했을 때, 답에 다다르지 못하는 상황이 있을 수 있기 때문이다. 따라서 무한 루프에 빠지거나, 혹은 이 부분을 거르는 코드를 작성해야 하는데 상당히 번거롭다.

이런 경우 오히려 BFS로 생각했을 때, 문제가 확 와닿는 경우가 많다. BFS로 탐색할 경우, 시간의 기준으로 완전 탐색하기 때문에 이 문제의 의도와 정확히 맞아 떨어진다. 최대한 짧은 시간에 답과 일치할 경우 반복문을 빠져나오면 되기 때문이다. 따라서 위치에 따른 시간을 저장할 필요가 있다.

이 때, 선택지에 $+1,-1$이 있고 중간중간 $\times 2$ 도 있어 중복되는 위치에 방문할 가능성이 있다. 이 부분의 시간 복잡도를 줄이기 위해 메모리를 사용하여 코드를 짰다.

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';
}

Reference

• 백준(1697번) - 숨바꼭질