[백준 1697번] 숨바꼭질

1697번: 숨바꼭질

from collections import deque

n, k = map(int,input().split())

aera = [-1]*100001
visited = [-1]*100001

def getNextLocation(n):
    return [n-1,n+1,n*2]

def bfs():
    visited[n] = 0
    queue = deque([n])

    while queue:
        v = queue.popleft()

        if v == k:
            return visited[v]
        
        for next in getNextLocation(v):
            if 0 <= next < 100001 and visited[next] == -1:
                visited[next] = visited[v] + 1
                queue.append(next)

    return -1

print(bfs())

이번 문제는 수빈이가 (현재 좌표-1), (현재 좌표+1), (현재 좌표*2)로 이동할 수 있다는 가정 하에 위치한 좌표 n 에서 동생이 위치한 좌표 k 까지 도착할 수 있는 최단 시간을 구하는 문제이다.

 

일단 수빈이와 동생의 좌표가 1차원 선상에 존재하기 때문에 1차원으로 위치 좌표와 방문 여부 리스트를 선언하고, BFS 알고리즘을 사용하여 (현재 좌표-1), (현재 좌표+1), (현재 좌표*2)를 탐색해가며 최단 시간을 구하였다.

 

그리고 사실 한 가지 더 고민해야 할 문제가 있는데, 수빈이와 동생의 위치가 0에서 100,000 사이라고 했지 수빈이가 이동 중에 반드시 0에서 100,000 사이에만 있어야한다는 조건은 없다. 예를 들어 100,000 밖으로 나갔다가 다시 안으로 올 수도 있다. 따라서 이 부분을 고려할 필요가 있다.

👉🏻 수빈이가 0에서 100,000 사이에서만 움직인다고 멋대로 가정을 하고 풀면 안된다 !

 

배운 점 및 느낀 점

1. DP나 DFS/BFS의 리스트를 선언할 때, 범위를 문제에서 주어진 대로 선언하면 안되고, 최대 어느 범위까지 이동할 수 있는지 고민해보고 선언하자.(추후에 범위로 인해 오류가 발생할 수 있다)