(Python)백준 코딩테스트 연습 - 숨바꼭질 3(13549)

1. 문제

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

13549번: 숨바꼭질 3

2. 풀이

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

# n, k : 수빈이와 동생의 위치
n, k = map(int, input().split())

positionList = [-1] * 100001

q = deque()
q.append(n)

positionList[n] = 0

while q:
    n_posi = q.popleft()
    if n_posi == k:
        print(positionList[n_posi])
        break
    for af_position in (n_posi-1, n_posi+1, n_posi*2):
        if 0 <= af_position < 100001 and positionList[af_position] == -1:
            if af_position == n_posi*2 and af_position != 0:
                q.appendleft(af_position)
                positionList[af_position] = positionList[n_posi]
            else:
                q.append(af_position)
                positionList[af_position] = positionList[n_posi] + 1

3. Feedback

 - 해결까지 참 오래걸린 문제이다.

 처음에는 브루트포스 알고리즘 개념을 적용하여 진행하려고 했지만, Recursion Error를 여러번 경험하면서 다른 알고리즘으로 접근이 필요하다고 생각했고, 이후 BFS 알고리즘을 적용하여 해결할 수 있었다.

 문제에서 제시한 *2의 이동시간이 0이라는 점을 주의하여 q 배열에 appendleft하여 해결할 수 있었다.