[백준/13549/Gold V] 숨바꼭질2 - BFS, 최단경로 깊이를 배열에 저장하기 with Python

문제✅

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

WHY? 알고리즘 선택 이유

• bfs → 최단 경로

 

HOW? 어떻게 풀었는가

• 문제점: 리스트에 [(0, 1), (0,2)] 이런식으로 시간까지 튜플로 넣는 방식에서 메모리 초과가 났다.
  • → 해결 : 시간은 따로 visited 배열을 두고 따로 관리하는 게 나음
  visited배열에는 각 숫자에 도달하기까지 걸린 시간을 누적함 → 최종적으로 visited[k]에는 도착지까지 걸린 최소 시간이 저장됨.

 

POINT! 기억할 부분

• 최단경로 구할때, 큐에 (현재, 경로) 이런식으로 각 데이터를 배열로 저장하지말고, 따로 visited배열을 만들어서 거기에 경로 길이를 저장하는게 메모리 초과가 더 안난다.

 

풀이1 - 메모리 초과

from collections import deque

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

queue = deque([(n, 0)])

while queue:
    x, t = queue.popleft()

    if x == k:
        print(t)
        break

    for i, next in enumerate((x-1, x+1, x*2)):
        if 0 <= next <= 100000:
            if i == 2:
                queue.append((next, t))
            else:
                queue.append((next, t + 1))

풀이2 - 메모리 초과 해결

from collections import deque

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

queue = deque([n])
visited = [-1] * 100001 # visited[현재위치] = 현재까지 걸린 최단 시간, 한번도 간적없으면 -1
visited[n] = 0

while queue:
    x = queue.popleft()

    if x == k:
        print(visited[x])
        break

    for next in (x-1, x+1, x*2):
        # 아직 한번도 안간 위치일 경우에만 지남
        if 0 <= next < 100001 and visited[next] == -1:
            if next == x*2:
                # 0초 걸리는 경우는 맨앞에 추가해준다
                queue.appendleft(next)
                visited[next] = visited[x]
            else:
                queue.append(next)
                visited[next] = visited[x] + 1