PS/Python
[Python] 백준 1697번: 숨바꼭질 - bfs
yoo.o
2020. 8. 17. 15:13
반응형
문제
1697번: 숨바꼭질
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가
www.acmicpc.net
풀이
bfs를 통해 재귀적으로 v-1, v+1, v*2의 위치를 찾아가면서 visited 배열을 통해 걸리는 시간을 관리했다.
빠트렸던것 두가지:
1. 동생의 위치와 내 위치가 이미 같을경우 -> 0으로 출력하고 break
2. visited 배열의 크기를 동생의 최대 위치인 100000으로 설정하면 안됨 ->
예. 수빈: 65000 동생: 100000인 경우 2*65000 = 130000
100000-65000 = 35000
130000-100000 = 30000 이니까 동생의 범위를 넘어서 갔다가 돌아올 경우도 고려를 해줘야한다.
import sys
from collections import deque
x, y = map(int, sys.stdin.readline().split(" "))
visited = [-1 for _ in range(150000)]
queue = deque()
queue.append(x)
visited[x] = 0
while queue:
v = queue.popleft()
if v == y:
print(visited[y])
break
if 0 <= v-1 <= 100000 and visited[v-1] == -1:
queue.append(v-1)
visited[v-1] = visited[v] + 1
if 0 <= v+1 <= 100000 and visited[v+1] == -1:
queue.append(v+1)
visited[v+1] = visited[v] + 1
if 0 <= 2*v <= 100000 and visited[2*v] == -1:
queue.append(2*v)
visited[2*v] = visited[v] + 1
반응형