[Python] 백준 13549번: 숨바꼭질 3

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

13549번: 숨바꼭질 3

import sys
input = sys.stdin.readline


def getMinTimeToCatch(N, K):
    todo = [(N, 0)]
    isVisited = [False]*100001
    isVisited[N] = True

    while todo:
        x, t = todo.pop(0)
        isVisited[x] = True

        if x == K:
            break

        if x-1 >= 0 and isVisited[x-1] == False:
            todo.append((x-1, t+1))
        if x+1 <= 100000 and isVisited[x+1] == False:
            todo.append((x+1, t+1))
        if x*2 <= 100000 and isVisited[x*2] == False:
            todo.insert(0, (x*2, t))

    return t


if __name__ == '__main__':
    N, K = map(int, input().split())

    minTimeToCatch = getMinTimeToCatch(N, K)
    print(minTimeToCatch)

범위가 100000까지로 매우 적은 범위이므로, 모든 가능성에 대해 고려를 해도 된다고 생각하였다. 따라서 나는, (위치, 소요된 시간)이라는 포멧으로 bfs를 돌리기로 하였다. 다만 여기서 중요한 것은, 해당 위치를 방문하였는지 여부를 나타내야한다는 것이다. 중복하여 방문할 시 시간 효율이 매우 떨어지기 때문이다.

 

이에 따라 getMinTimeToCatch() 함수를 작성하였다. 단순한 bfs 형태이지만, 설명해야할 것이 몇 가지 있다.

- todo에서 pop을 했을 때, 해당 위치가 K와 같을 시 break 해준다.

- x-1, x+1, x*2 연산에 대해 각각, 범위를 확인해주고 방문 여부가 False일 때에만 todo에 추가해준다.

- 다만, x*2 연산의 경우에는 append()가 아니라, insert()를 사용하여 맨 앞에다 추가해주었는데, 해당 연산은 시간이 추가되지 않기 때문이다.

 

이렇게 하여 break로 탈출해준 뒤, t값을 리턴해주면 된다.