백준 1697번 파이썬 _ 숨바꼭질 (실버1)

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제유형: BFS

 

문제풀이 

<BFS를 이용한 풀이>

• answer배열 = 해당노드를 몇초에 처음 방문하게 되는지 저장하기 위한 배열 + 방문여부또한 체크할수있다.
• 큐에서 노드하나 빼서 해당노드를 기준으로 -1, +1, 2배를 해준다.
• 결과로 나온 3개의 노드를 순회하며 아직 방문전이고 ((이미 방문한 노드일경우 중복해서 큐에 넣을필요가 없기때문)) n이아니면 (만약 어떤 이동을 수행한 결과가n이면 결국 자기자신이므로 볼필요없음)) 큐에 추가함
• 위 과정을 큐가 빌때까지 반복하다가 큐에서 꺼낸노드가 목적지 노드일경우 break로 while문을 빠져나온다

정답코드 : 

import sys
input = sys.stdin.readline

# 걸을때 1초후에 x-1, x+1로 이동
# 순간이동일때 1초후에 2*x로 이동
# 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이몇초?

from collections import deque
n,k = map(int, input().split())
answer = [0]*100001
q = deque([n])

while q:
    x = q.popleft()
    if x==k:
        break
    time = answer[x] + 1    #직전에 방문했던 노드의 방문시간에 1을 더해줌으로 시간경과를 표현
    t = [x+1, x-1, 2*x]
    for nx in t:
        if nx >= 0 and nx <= 100000 and answer[nx] == 0 and nx != n: #방문전이고 n이 아니면
            answer[nx] = time    # 처음 방문하는 노드에 방문표시 + 몇초에 방문했는가 
            q.append(nx)
            
print(answer[k])