문제 링크
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
- bfs 문제
- 큐에 방문한 위치와 몇초에 방문했는지 기록
- 위치를 이동했을 때마다 x+1, x-1, x*2에 대하여 범위에 해당하고 방문하지 않았으면 큐에 삽입하는 과정 반복
- 동생이 있는 위치에 도착했을 때 몇초가 걸렸는지 출력
from collections import deque
n, k = map(int,input().split())
q = deque()
q.append((n,0))
# 방문 표시
visited = [False] * 100001
visited[n] = True
while q:
x, s = q.popleft()
if x == k:
print(s)
break
else:
for i in (x-1, x+1, x*2):
if 0 <= i <= 100000 and not visited[i]:
q.append((i,s+1))
visited[i] = True
'개발 > algorithm' 카테고리의 다른 글
[백준 2178번] 미로 탐색 - python (0) | 2022.02.16 |
---|---|
[백준 1992번] 쿼드트리 -python (0) | 2022.02.16 |
[백준 1074번] Z - python (0) | 2022.02.15 |
[백준 18870번] 좌표 압축 - python (0) | 2022.02.15 |
[백준 1931번] 회의실 배정 - python (0) | 2022.02.15 |