백준-13913-숨바꼭질 4

문제

숨바꼭질 4

풀이

문제조건 해석

n에서 k로 가는 가장 빠른 경로 찾는 문제

정답으로 최단 시간뿐만 아니라 경로또한 출력해야 한다.

알고리즘

BFS 알고리즘으로 해결해야한다.

또한, 해당 위치로 도달하기 전 위치를 저장하는 배열 parent를 설정해야 한다.

• 모든 위치에 대해 모든 이전 경로를 저장하는 자료구조(딕셔너리) 사용하면 메모리 초과난다.

코드

# 모든 위치에 대해 경로 저장하는 방법 --> 메모리 초과
from collections import deque, defaultdict
n, k = [int(_) for _ in input().split()]

visited = defaultdict(list)
visited[n].append(n)
queue = deque([n])
step = 0
while queue:
    for _ in range(len(queue)):
        current = queue.popleft()
        if current == k:
            print(step)
            queue = None
            break
        if current-1 not in visited:
            visited[current-1] = visited[current] + [current-1]
            queue.append(current-1)
        if current+1 not in visited:
            visited[current+1] = visited[current] + [current+1]
            queue.append(current+1)
        if 2*current not in visited:
            visited[2*current] = visited[current] + [2*current]
            queue.append(2*current)
    step += 1
for x in visited[k]:
    print(x, end=' ')

# 이전 위치(부모 노드)만 저장하는 배열을 이용하면 해결된다.
from collections import deque
n, k = [int(_) for _ in input().split()]
MAX_NUM = 100000
parent = [False for _ in range(MAX_NUM+1)] # 부모 노드를 가리키는 배열
visited = set()
queue = deque([n])
parent[n] = n
step = 0
while queue:
    for _ in range(len(queue)):
        current = queue.popleft()
        if current == k:
            print(step)
            queue = None
            break
        if current > 0 and current-1 not in visited:
            visited.add(current-1)
            parent[current-1] = current
            queue.append(current-1)
        if current < MAX_NUM and current+1 not in visited:
            visited.add(current+1)
            parent[current+1] = current
            queue.append(current+1)
        if 2*current <= MAX_NUM and 2*current not in visited:
            visited.add(2*current)
            parent[2*current] = current
            queue.append(2*current)
    step += 1

answer = []
while k != n: # 경로 역추적
    answer.append(k)
    k = parent[k]
answer.append(n)

for i in answer[::-1]:
    print(i, end=' ')

배운점

• BFS의 경로를 저장할 때는 부모 노드만을 저장하는 자료구조 이용하자.
  • 각 노드는 최단 시간에 단 한번 방문한다.