[BOJ 1697] 숨바꼭질 파이썬(Python) 풀이

문제보기

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

1697번: 숨바꼭질

문제 해설

완전 탐색 방법에는 다음과 같은 방법들이 있습니다.

• Brute Force : for문과 if문을 이용해 처음부터 끝까지 탐색하는 방법
• 비트마스크
• 순열 : 순열의 시간 복잡도는 O(N)
• 백트래킹
• BFS

이 문제는 BFS로 풀 수 있습니다.

역시나 처음에는 노가다를 좀.. 해봤습니다

수빈이의 위치는 -1, +1, X2로 이동할 수 있습니다. 위 예시에서 볼 수 있듯이 DFS로 풀 경우, 무한 루프에 빠지게 발생하게 됩니다.

 

정답 코드

from collections import deque


def bfs():
    q = deque()
    q.append(N)
    while q:
        v = q.popleft()
        if v == K:
            print(time[v])
            return
        for next_step in (v-1, v+1, v*2):
            if 0 <= next_step < MAX and not time[next_step]:
                time[next_step] = time[v] + 1
                q.append(next_step)


MAX = 100001
N, K = map(int, input().split())
time = [0]*MAX
bfs()

리스트(List)를 큐로 사용하면 절대 안됩니다. 큐는 반드시 collections.deque를 써야 합니다.

queue.Queue는 멀티스레딩을 위해 만들어진 큐이고 매우 느립니다.