[백준13913/골드4] 숨바꼭질 4 - Python

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

 

메모리나 시간초과 생각 안하고 바로 q에 이동 경로를 함께 append하면서 bfs로 풀었는데 시간초과 났다. 어쩐지 이게 왜 골드일까 생각했어야했다.

 

# 실패 코드 1

from collections import deque

N, K = map(int, input().split())

q = deque([(0, N, [N])])
visited = [False] * 100001
visited[N] = True

while q:

    ct, cc, c_lst = q.popleft()

    if cc == K:
        print(ct)
        print(*c_lst)
        break

    for nc in [cc-1, cc+1, cc*2]:
        if 0 <= nc < 100001 and not visited[nc]:
            visited[nc] = True
            q.append((ct+1, nc, c_lst + [nc]))

 

그래서 이번에는

1. bfs 이동하면서 visited 배열에 이전 노드를 부모로 등록

2. 결과 찾았으면 dfs로 부모 노드 찾기

이렇게 했는데 이것도 메모리 초과났다.

 

# 실패 코드 2

import sys
from collections import deque

sys.setrecursionlimit(10**6)

N, K = map(int, input().split())

q = deque([(0, N)])
visited = [-1] * 100001
visited[N] = True
visited[N] = N


def parent(n, lst):
    if n == N:
        return lst

    result = parent(visited[n], [visited[n]] + lst)

    if result:
        return result

while q:

    ct, cc = q.popleft()

    if cc == K:
        print(ct)
        print(*parent(K, [K]))
        break

    for nc in [cc-1, cc+1, cc*2]:
        if 0 <= nc < 100001 and visited[nc] == -1:
            visited[nc] = cc
            q.append((ct+1, nc))

 

 

그래서 마지막으로 부모노드를 찾을 때 while문으로 탐색했더니 성공했다.

 

# 성공 코드

from collections import deque

N, K = map(int, input().split())

q = deque([(0, N)])
visited = [-1] * 100001
visited[N] = True
visited[N] = N

while q:

    ct, cc = q.popleft()

    if cc == K:
        print(ct)
        break

    for nc in [cc-1, cc+1, cc*2]:
        if 0 <= nc < 100001 and visited[nc] == -1:
            visited[nc] = cc
            q.append((ct+1, nc))

result = []
cur = K
while cur != N:
    result.append(cur)
    cur = visited[cur]
result.append(N)

print(*result[::-1])

 

 

이렇게 실패하기 전에 최적의 방법을 찾기 위해 고민좀 많이 하고 풀어야겠다.