공부/Algorithm
[BOJ] 1697 숨바꼭질
mariabeetle
2021. 1. 31. 22:22
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
-
deque를 사용한 bfs로 품
from collections import deque def bfs(start, end): cnt = 0 # [현재 위치, 현재까지 걸린 시간] pair queue = deque([[start, cnt]]) # 문제 조건에 0~100000 위치까지로 명시됨. # 방문안한 위치만 queue에 값 추가해서 탐색 visited = [False] * 100001 while queue: pos, cnt= queue.popleft() if visited[pos] == False: visited[pos] = True if end == pos: return cnt else: cnt += 1 if pos * 2 <= 100000: queue.append([pos*2, cnt]) if pos+1 <= 100000: queue.append([pos+1,cnt]) if pos-1 >= 0: queue.append([pos-1, cnt]) return cnt s, e = map(int, input().split()) print(bfs(s, e))