[BOJ/백준] 1697번 숨바꼭질 (Python 파이썬)

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

1697번: 숨바꼭질

시간	제한메모리	제출제출	정답	맞힌 사람	정답 비율
2 초	128 MB	158993	45289	28409	25.059%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

문제 풀이 전략

DFS vs BFS

문제를 보자마자 어떤 search를 진행할 것인지 판단할 수 있어야 합니다. 간단하게 정리를 해보자면,

1. DFS가 유리한 경우
   - 재귀적인 특징과 백트래킹을 이용하여 모든 경우를 하나씩 전부 탐색하는 경우
   - Graph의 크기가 클 경우
   - Optimal한 답을 찾는 것이 아닌 경우
   - 경로의 특징을 저장해야 하는 경우 ex) 경로의 가중치, 이동 과정에서의 제약
2. BFS가 유리한 경우
   - 최단 거리 or 최단 횟수 구하는 경우
   - Optimal한 답을 찾는 경우, BFS는 가장 처음 발견되는 해답이 최단 거리이다!
   - 탐색의 횟수를 구해야 하는 경우(7576번 토마토 문제)

그렇다면, 해당 문제는 BFS를 사용하는 것이 유리합니다!

 

DP

해당 문제에 간단하게 DP 기법을 사용하면 효율적입니다. 

대략적인 전략은 우선 충분한 1차원 리스트를 초기화 시킨 뒤,  BFS를 돌면서 이동할 때 마다 해당 자리에 time 값을 저장합니다. 이때 Tabulation을 이용하여 값을 누적시키면서 증가시키게 되면, BFS가 종료될 때 동생이 있는 자리인 K에는 최종 time값이 들어있을 것입니다.

 

문제 풀이

import sys
from collections import deque
input = sys.stdin.readline

# 범위 계산에 사용할 MAX값 선언 - N,K의 최댓값
MAX = 10**5


def BFS(N, K):
    graph = [0] * (2*MAX + 1)
    queue = deque([N])
    while queue:
        x = queue.popleft()

        # K : 동생 자리
        if x == K:
            print(graph[K])
            return
        # 순간이동 -> 무한 루프 방지를 위해서 순간 이동 시 걸어가는 경우보다 동생과 가까워 질 경우에만 사용
        #    1. 이동 전 조건문에서 graph 범위 확인 필요
        #    2. 이동할 자리의 값이 0인지 확인
        #       만약 0이 아니라면, 이미 "다른 경로"로 해당 자리를 거쳤고,
        #       그 자리 값에 1을 더하는 행위는 곧, 현재의 경로가 최단 경로가 아님을 의미한다.
        if graph[2*x] == 0 and abs(K-2*x) < abs(K-x):
            queue.append(2*x)
            graph[2*x] = graph[x] + 1
        if x + 1 <= MAX and graph[x+1] == 0:
            queue.append(x+1)
            graph[x+1] = graph[x] + 1
        if x - 1 >= 0 and graph[x-1] == 0:
            queue.append(x-1)
            graph[x-1] = graph[x] + 1


N, K = map(int, input().split())
BFS(N, K)

조심해야 할 점은, "순간 이동"의 경우의 수 때문에 현재 수빈의 위치, x가 MAX를 벗어날 수 있다는 점입니다. 

예를 들어 수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있습니다. 따라서 graph의 크기를 MAX보다 크게 초기화시켜야 에러가 나질 않습니다.

 

BFS를 살펴보면, 탐색의 조건은 크게 2가지였습니다.

1. graph 범위 확인 
    "걷기"의 경우 0 ~ MAX 범위 내에서만 이동이 가능하고, "순간 이동"의 경우 MAX를 넘을 수는 있지만, 제약이 없다면 무한히 append되기 때문에 loop에 빠지게 됩니다. 따라서 순간 이동은 걷는 경우보다 동생에게 더 가까워 질 경우에만 사용하는 것으로 합니다.
2. 이동할 자리는 값이 0 
    만약 이동할 자리의 값이 0이 아니라고 해봅시다. 이는 곧 해당 자리를 거치는 다른 경로가 이미 존재함을 의미합니다. 그렇다면 여기에 1을 더하는 행위는 곧 현재의 경로가 최단 경로보다 더 큰 time값을 갖도록 합니다.
   이를 방지하기 위해서 항상 이동한 적이 없는 자리로 이동해야만 합니다.

조건대로 BFS를 구현하면 문제 풀이 끝입니다!

 

다른 분들의 코드를 살펴보니 제 코드보다 깔끔하여 남겨봅니다.

from collections import deque
import sys
input=sys.stdin.readline

def bfs():
    q=deque()
    q.append(n)
    while q:
        now=q.popleft()
        if now==k:
            return
        for i in (now-1,now+1,now*2):
            if 0<=i<100001 and dp[i]==0:
                dp[i]=dp[now]+1
                q.append(i)

n,k=map(int,input().split())
dp=[0]*100001

bfs()
print(dp[k])

여기서는 for문을 통해서 이동의 경우의 수대로 반복을 진행하였고, 조건도 깔끔하게 1줄로 통일되었습니다.

하지만 여기서는 순간 이동시 MAX를 벗어나는 경우를 허용하지 않았네요..?

for i in (now-1,now+1,now*2):
     if 0<=i<100001 and dp[i]==0:
          dp[i]=dp[now]+1
          q.append(i)

 

결과는 모두 정답처리가 되었습니다. 문제에서 "순간 이동시 MAX를 벗어나는 경우"에 대해서 명확한 제한을 두지 않았는데, 모두 정답 처리된 것이 조금 이상합니다. 제가 놓친 부분이 있는 것 같은데 잘 모르겠네요..