[Python] 백준 1697번: 숨바꼭질 - bfs

문제

1697번: 숨바꼭질

 

풀이

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