백준 [13913] 숨바꼭질4(Python3)

지문 해석

현재 위치를 X라 할 때, 일정한 범위 (X - 1, X + 1, X * 2)를 탐색한다.

매 이동엔 1초가 필요하니, 큐를 이용하는 BFS 방식이 필요했다.

방문 여부 체크에 관해서는 Boolean 값이면 충분했다.

최적의 탐색 비용의 경우, 큐 삽입 때, 기존 비용 + 1을 하면 간단히 해결됐다.

하지만, 지나온 경로를 표시하는 부분 해결에서 문제를 겪었다.

 

지나온 경로 문제 해결

1, 2번은 틀린 풀이다.

1. BFS 한 번 더 사용

데이터 범위가 작기 때문에 N -> K로 가는 BFS의 시간 복잡도가 적은것을 이용해

K -> N으로 다시 BFS를 할까 생각했다.

 

하지만, 이 과정은 코드가 너무 길어지고, 되돌아간 위치가 최단 경로 중 하나인지에 대한 검증이 필요했기 때문에

좋은 해결책이 아니라고 생각했다.

 

2. 큐에 지나온 경로 삽입

그래서 생각한 것이, 현재 위치가 지나간 경로를 같이 큐에 넣어준 것이었다.

범위가 충분히 적은 경우엔 정답이 나왔다.

하지만, 경로 전체를 큐에 계속 넣기 때문에 범위가 넓어진다면, 매 탐색마다 큐에 넣어야 할 데이터가 증가해

시간 초과가 발생했다.

 

3. 어떤 X를 통해 이동했는지만 기록

dp스러운 풀이였다.

현재 위치를 X라 하고, 다음 이동할 위치를 Y라 하자.

Y의 경우엔 X를 통해 왔단 것이 중요하지 이 X이전의 경로는 별로 중요하지 않다.

이 X도 결국은 어떤 장소 Z에서 이동된 것이기 때문에 그 어떤 장소 Z의 위치만 중요하지

이 Z로 가는 길이 무엇인지는 중요하지 않다.

따라서, 일차원 배열을 초기화해 각 지점이 어떤 지점을 통해 왔는지를 기록했다.

 

코드

from collections import deque
N, K = map(int, input().split())
visit = [False] * 100001
record = [0] * 100001
q = deque()
q.append((N, 0))
while q:
    hereX, hereC = q.popleft()
    if hereX == K:
        print(hereC)
        index = hereX
        answer = [index]
        for _ in range(hereC):
            index = record[index]
            answer.append(index)
        answer.reverse()
        print(*answer)
        break
    if hereX <= 50000:
        if not visit[hereX * 2]:
            visit[hereX * 2] = True
            record[hereX * 2] = hereX
            q.append((hereX * 2, hereC + 1))
    if hereX > 0:
        if not visit[hereX - 1]:
            visit[hereX - 1] = True
            record[hereX - 1] = hereX
            q.append((hereX - 1, hereC + 1))
    if hereX < 100000:
        if not visit[hereX + 1]:
            visit[hereX + 1] = True
            record[hereX + 1] = hereX
            q.append((hereX + 1, hereC + 1))