Python으로 푸는 백준 1697. 숨바꼭질

백준 1697. 숨바꼭질

수빈이와 수빈이의 동생이 숨바꼭질을 하고 있다. 수빈이가 걷거나 순간이동을 하여 동생을 찾아낼 수 있다.

가장 최소한의 움직임으로 동생을 찾을 수 있는 경우가 몇 초 후인지 알아낼 수 있도록 코드를 구현해보자.

백준에서 푼 문제 리스트 보러 가기

백준에서 문제 보기

github에서 코드 보기

문제 조건

수빈이는 걷거나 순간이동을 할 수 있다.

- 수빈이의 현재 위치를 X라고 했을 때, 걷는다면 1초 후 (X - 1) 혹은 (X + 1)에 위치한다.

- 수빈이의 현재 위치를 X라고 했을 때, 순간이동을 한다면 1초 후 2*X에 위치한다.

문제 풀이

숫자가 써 붙여진 10만개의 방을 오가면서 수빈이와 수빈이의 동생이 숨바꼭질을 하고 있다고 생각하고 문제를 푼다. 

수빈이가 현재 있는 위치 X에서 이동할 수 있는 방은 (X - 1), ( X+ 1), (2*X)이다. 이동한 방에서 또다시 이동가능한 방도  똑같이  (X - 1), ( X+ 1), (2*X), 3가지이다. 

여러가지 경우의 수를 모두 탐색하다보면 들어갔던 방을 또 들어갈 수도 있는데, 그때마다 동생이 있는 방에 도달할때까지 초를 다시 세려면 무의미할 것이다.

그래서 어떤 숫자가 적힌 방을 수빈이가 방문했을 때, 수빈이는 몇 초만에 이곳에 왔는지 기록해둔다.

수빈이가 이전에 방문했던 방을 다시 방문하게 되었을 때, 지금 이 방을 방문할 때 걸렸던 시간보다 방문에 써둔 시간이 더 적은 시간일 경우에는 (어차피 최소 시간이 되기는 글렀으므로) 더 이상 탐색을 하지 않는다. (가지치기)

반면에 방문에 써둔 시간보다 더 적은 시간이 걸려서 해당 방에 도착했을 경우에는 최소 시간이 될 가능성이 있으므로 탐색을 계속해 나간다. 

모든 탐색이 종료되고 나면, 동생이 있는 방에는 동생을 찾기 위해 올 수 있는 최소 시간이 적혀 있을 것이다.

숨바꼭질 문제에서는 백트래킹 전략을 활용하여 가지치기를 통해 시간 복잡도를 줄이고 해를 구할 수 있다.

DFS, BFS가 가능한 모든 경우를 탐색 하는 방법이라고 했을 때, 백트래킹은 현재 상태를 보관하고 나중에 이를 다시 활용하는 방식이다. 

백트래킹 전략으로 파이썬을 푼 코드는 다음과 같다.

파이썬 코드

import sys
from collections import deque
input = sys.stdin.readline
 
 
def solve():
    while q:
        cur = q.popleft()
        if cur == k:
            return visit[cur]
        nextPos(cur - 1, cur)
        nextPos(cur + 1, cur)
        nextPos(cur * 2, cur)
 
 
def nextPos(nex, cur):
    # nex 지점이 범위 내에 있고
    # 한번도 방문하지 않았거나, 최소 time으로 해당 방을 방문한 경우
    if maxSize > nex >= 0 and (0 == visit[nex] or visit[cur] + 1 < visit[nex]):
        visit[nex] = visit[cur] + 1
        q.append(nex)
 
if __name__ == "__main__":
    n, k = map(int, input().split())
    maxSize = 100001
    visit = [0] * maxSize
    q = deque([n])
    print(solve())

#1697 숨바꼭질 #백준 1697 숨바꼭질 #백준 1697 python ##1697 숨바꼭질 파이썬