[백준] 1697 - 숨바꼭질 (Python)

문제 설명

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

---

문제 풀이

지금까지 풀었던 BFS 문제들은 2차원 리스트에서 상하좌우로 탐색하는 문제였다면

이 문제는 1차원 리스트에서 탐색하는 문제다

기존 문제들과 푸는 방법이 살짝 달라서 고민을 좀 하고 풀었다

 

제한사항을 읽어보고 아무 생각 없이 리스트의 크기를 100,000으로 지정했는데,

문제를 풀고 나서 코드를 다시 보니 탐색하다보면 범위를 넘을 수도 있다

수빈이와 동생의 위치가 0 < x < 100,000 인 것이지 이 범위가 탐색 범위는 아니라는 것,,,,,

오히려 범위를 넘은 후 돌아오는 방법이 더 빠른 경우도 있지 않을까.. 생각했다

 

이번 문제는 운좋게도 통과했지만 다른 비슷한 문제가 나왔을 때 범위를 넘는 경우도 있을 것 같다

문제를 잘 읽어보고 BFS 수행 범위를 지정해야겠다 ...

이 문제에서는 2*n 이동이 제일 크게 이동하기 때문에 최대 탐색 범위는 200,000 이다!

 

from collections import deque

def bfs(v):
    queue.append(v)
    while queue:
        v = queue.popleft()
        if v == k:
            return visited[v]
        for i in (v-1, v+1, 2*v):
            if 0 <= i <= 100000 and not visited[i]:
                queue.append(i)
                visited[i] = visited[v] + 1


n, k = map(int, input().split())
visited = [0 for _ in range(100001)]
queue = deque()
print(bfs(n))