[백준/파이썬] 13549번: 숨바꼭질 3

문제

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

풀이

• 시작 지점: N, 도착 지점: K
• X에 위치할 때 걷는다면, 1초 후에 X-1 OR X+1로 이동
• X에 위치할 때 순간이동을 한다면, 0초 후에 2*X로 이동

이 문제는 수빈이가 위치한 지점(N)에서 동생이 위치한 지점(K)의 최단 경로를 구하는 문제입니다.
BFS를 활용했습니다.

def bfs():
    visited = [False] * 100001 # 방문 여부
    cnt = [0] * 100001 # 각 위치에서 이동 시간
    queue = deque([n])
    visited[n] = True # 방문 처리

문제에 제시된 최대 범위 100001을 이용해 방문 여부를 확인할 배열과 이동 시간 배열을 선언했습니다.
queue에 초기값(수빈이의 위치)을 삽입, 방문 처리

    while queue:
        v = queue.popleft()
        
        # 순간이동
        if 0 <= v*2 < 100001 and not visited[v*2]:
            visited[v*2] = True # 방문 처리
            cnt[v*2] = cnt[v] # 시간 업데이트
            queue.append(v*2) # queue에 추가

		# 걷기
        if 0 <= v-1 < 100001 and not visited[v-1]:
            visited[v-1] = True
            cnt[v-1] = cnt[v] + 1
            queue.append(v-1)
            
        if 0 <= v+1 < 100001 and not visited[v+1]:
            visited[v+1] = True
            cnt[v+1] = cnt[v] + 1
            queue.append(v+1)

탐색하려는 위치에서의 값이 범위 내에 존재 && 방문한 적 없는 위치라면 탐색 시작

• 순간이동은 0초가 소모되므로 현재 위치에서의 시간을 그대로 삽입
• 걷기는 1초가 소모되므로 현재 위치에서의 시간 + 1을 삽입

		if v == k:
			return cnt[v]

마무리로 탐색하려는 위치가 동생의 위치와 같다면 return

코드

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

def bfs():
    visited = [False] * 100001
    cnt = [0] * 100001
    queue = deque([n])
    visited[n] = True
    
    while queue:
        v = queue.popleft()
        
        if v == k:
            return cnt[v]
        
        if 0 <= v*2 < 100001 and not visited[v*2]:
            visited[v*2] = True
            cnt[v*2] = cnt[v]
            queue.append(v*2)
        
        if 0 <= v-1 < 100001 and not visited[v-1]:
            visited[v-1] = True
            cnt[v-1] = cnt[v] + 1
            queue.append(v-1)
            
        if 0 <= v+1 < 100001 and not visited[v+1]:
            visited[v+1] = True
            cnt[v+1] = cnt[v] + 1
            queue.append(v+1)
    
if __name__ == "__main__":
    n,k = map(int,input().split())
    print(bfs())