숨바꼭질 3

순간이동을 할 때, 100,000 이하의 점에 대해서는 모두 갈 수 있도록 했어야 했는데, 100,000 미만의 점에 대해 가도록 코드를 짜서 한동안 헤맸다.

문제분석

숨바꼭질 문제에 순간이동이 추가된 문제다. 숨바꼭질 2에서는 1초 후 순간이동을 할 수 있었고, 이 문제에서는 0초 후 순간이동을 할 수 있게 되었다. 나머지 조건들은 동일하다.

  • 이 조건들을 활용해 BFS와 DP를 이용해 탐색을 한다.
  • BFS를 진행하며, deque에서 pop되어 나오는 점들 중 하나를 a라고 하자.
  • 100,000이하의 점들에 대해 (2^N)*a, a-1, a+1를 탐색하고, 이중에 k가 존재하지 않는다면, 다시 deque에 추가해 BFS를 진행한다.

CODE

import sys
read=sys.stdin.readline
from collections import deque
n,k=map(int,read().split())

len=100_000

point=deque([n])
dp=list(-1 for _ in range(len*2+1))
dp[n]=0

while point:
    a=point.popleft()
    if a==k:
        print(dp[a])
        break
    else:
        tmp=a
        while tmp<len*2 and tmp>=1:
            if dp[tmp]==-1:
                point.append(tmp)
                dp[tmp]=dp[a]
            tmp=tmp*2


        if a-1>=0 and dp[a-1]==-1:
            dp[a-1]=dp[a]+1
            point.append(a-1)
        if a+1<=len*2 and dp[a+1]==-1:
            dp[a+1]=dp[a]+1
            point.append(a+1)

Plus - 경로 확인

‘5 100,000’이 입력으로 주어질 때, 5가 나와야하는데 8이 출력되어 고민을 했다. 이 입력에 대해서는 손으로 써보면서 생각하기에는 무리가 있어서 코드로 작성한 후 눈으로 확인해 보았다.

아래의 코드를 실행시키면 다음과 같이 출력된다.

100000
3125
3124
781
780
195
196
49
48
6
5
  • 위와 같이 출력되어야 했었는데 문제를 풀면서 100,000미만의 점에 대해 순간이동 하도록 코드를 짰다. ‘=’를 빼먹은 것이다. 이를 발견하지 못해 아래의 코드를 만들면서 30분 동안 머리를 싸매고 고민해야했다…


CODE - 경로 확인 코드

import sys
sys.stdin = open("input.txt","rt")
read=sys.stdin.readline
from collections import deque
n,k=map(int,read().split())

len=100_000

point=deque([n])
dp=list(-1 for _ in range(len+1))
save=list(-1 for _ in range(len+1))
dp[n]=0

while point:
    a=point.popleft()
    if a==k:
        print(dp[a])
        break
    else:
        tmp=a
        while tmp<len and tmp>=1:
            if dp[tmp]==-1:
                point.append(tmp)
                dp[tmp]=dp[a]
                save[tmp]=a
            tmp=tmp*2


        if a-1>=0 and dp[a-1]==-1:
            dp[a-1]=dp[a]+1
            point.append(a-1)
            save[a-1]=a
        if a+1<=len and dp[a+1]==-1:
            dp[a+1]=dp[a]+1
            point.append(a+1)
            save[a+1]=a
x=k
while True:
    print(x)
    x=save[x]
    if x ==-1 : break


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]

✔ - 2020.12.06