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

백준 1697 - 숨바꼭질

---

* 풀이과정

 

우선, 최단 시간을 찾는 문제이기 때문에 BFS를 활용한다.

 

1) 위치별 도달하는 최단 시간을 저장할 배열, 방문 처리 배열을 선언한다.

2) 큐에 수빈이의 위치를 넣고, 방문 처리한다.

3) 문제에서 수빈이가 갈 수 있는 방향은 3가지(+1, -1, *2)이므로, 방문 여부를 체크하여 큐에 넣는다.

 

※ 수빈이가 갈 수 있는 3가지 방향을 if 문으로 나누었는데, for in을 사용하면 중복 코드를 줄일 수 있다.

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

time = [0 for _ in range(100001)]
visited = [False for _ in range(100001)]

def bfs(X):
    q = deque([X])
    visited[X] = True

    while q:
        pX = q.popleft()

        if pX == K: 
            print(time[pX])
            return
        
        for nX in (pX+1, pX-1, 2*pX):
            if 0 <= nX <= 100000 and not visited[nX]:
                time[nX] = time[pX]+1
                q.append(nX)
                visited[nX] = True

		# for in 문 사용하기 이전의 코드
        # if 0 <= pX + 1 <= 100000 and not visited[pX+1]:
        #     time[pX+1] = time[pX] + 1
        #     q.append(pX+1)
        #     visited[pX+1] = True
        # if 0 <= pX - 1 <= 100000 and not visited[pX-1]:
        #     time[pX-1] = time[pX] + 1
        #     q.append(pX-1)
        #     visited[pX-1] = True
        # if 0 <= 2*pX <= 100000 and not visited[2*pX]:
        #     time[2*pX] = time[pX] + 1
        #     q.append(2*pX)
        #     visited[2*pX] = True
    
bfs(N)