[알고리즘] 백준 1697번 : 숨바꼭질 (파이썬)

백준 1697번 : 숨바꼭질
난이도 : 실버 1

- 문제 소개

- 조건

• 없음

- 코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

def bfs(v):
	q = deque([v])
    while q:
    	v = q.popleft()
        if v == m:
        	return visited[v]
        for i in (v-1, v+1, 2*v):
        	if 0 <= i <= 100000 and not visited[i]:
            	visited[i] = visited[v] + 1
                q.append(i)
visited = [0 for i in range(100001)]
print(bfs(n))

- 해설

최단시간을 구하기 위해서 생각할 수 있는 알고리즘은 DFS와 BFS가 있는데, 그 중 BFS를 통해 해결할 수 있는 문제입니다. 갈 수 있는 위치는 v-1, v+1, 2*v 총 3가지 경우이며, while문을 돌면서 i가 정해진 범위에 있고, 방문하지 않았던 곳에 방문하면 +1을 해주며 만약 q에 들어간 v가 최종 위치인 m과 같으면 방문한 횟수가 기록된 visited[v]를 return해서 출력해줍니다.