[백준 파이썬] 1697 숨바꼭질

📌문제 출처

백준 단계별 문제풀이 - 그래프와 순회
https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

❓ 문제

❗ 풀이

• bfs 활용

📗 풀이 코드

import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
arrival = {i:0 for i in range(0,100001)} # 해당 지점 방문 여부
def bfs(cur,cnt): # 현재 위치와 이동 시간을 통해 다음 이동 위치를 정하는 bfs 함수 생성
    stack = deque()
    stack.append([cur,cnt])
    while stack:
        cur,cnt = stack.popleft()
        if cur == k :
            return cnt
        if arrival[cur]: # 이미 방문한 적이 있다면 통과
            continue
        arrival[cur] = 1
        cnt += 1
        # 0이면 +1만 가능 / 50001~99999 +1,-1만 가능 / 1~50000이면 셋 모두 가능 / 100000이면 -1만 가능
        if not cur:
            stack.append([cur+1,cnt])
        elif 1 <= cur <= 50000:
            stack.append([cur-1,cnt])
            stack.append([cur+1,cnt])
            stack.append([cur*2,cnt])
        elif 50001 <= cur <= 99999:
            stack.append([cur-1,cnt])
            stack.append([cur+1,cnt])
        else :
            stack.append([cur-1,cnt])
print(bfs(n,0))

📗 코드 해설

• 현재 위치(cur)와 총 이동 시간(cnt)를 인자로 작동하는 함수 bfs를 생성
• cur의 조건에 따라 향후 이동가능한 위치를 stack에 넣어둔다.
• 다음 위치로 이동 후에는 해당 위치가 동생의 위치라면 그때까지의 이동시간을 반환한다.
  이동시간이 점점 늘어나는 순으로 stack에 쌓이므로 이후의 stack은 확인하지 않아도 된다.
• 한번 방문한 위치는 다시 방문하지 않기 위해 arrival이라는 dictionary에 위치별로 0을 넣어주고,
  방문할 때마다 1로 변경해준다.
• 이동 후에 방문한 적이 있는 위치라면 추가 확인을 이어가지 않는다.