[Python/파이썬] 백준 알고리즘 13913 - 숨바꼭질 4 (BFS)

 

 

 

<풀이>

경로를 표현해야해서 처음에는 DFS로 탐색해야하나..? 생각했다

하지만 BFS로도 충분히 해결할 수 있었다.

경로에 대한 배열을 따로 만들어 최단경로에 대한 값을 저장하며 해결하는 것이다.

# 아래는 따로 path 배열을 안만들고 파라매터로 받아 처리한건데 시간초과 나온다...
# 왜 시간초과가 나올까..?
import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
road = [0] * 100001

queue = deque()
queue.append([N])
road[N] = 1
while queue:
    pathList = queue.popleft()
    popN = pathList[-1]
    if popN == K:
        print(road[K]-1)
        print(" ".join(map(str, pathList)))
        break
    for newN in (popN-1, popN+1, 2*popN):
        if 0<=newN<100001 and road[newN] == 0:
            road[newN] = road[popN] + 1
            queue.append(pathList + [newN])

그래서 처음에 위와 같이 코드를 작성하였다.

풀이상에는 문제가 없다고 생각들고 맞는것 같은데 자꾸 시간초과가 나서 틀렸다..

 

다른 사람들의 풀이를 참고하니 path라는 배열을 따로 만들어 path[newN]에서 popN인덱스를 참조하게 만들어 풀었다.

학교 알고리즘 수업에서도 비슷한 방법의 풀이를 봤었는데 다시 복습해봐야겠다.

 

그렇게 다시 작성한 풀이는 아래와 같다.

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
road = [0] * 100001
path = [0] * 100001

queue = deque()
queue.append(N)
road[N] = 1
while queue:
    popN = queue.popleft()
    if popN == K:
        print(road[K] - 1)
        pathResult = []
        while popN != N:
            pathResult.append(path[popN])
            popN = path[popN]
        pathResult.reverse()
        pathResult.append(K)
        print(" ".join(map(str, pathResult)))
        break
    for newN in (popN-1, popN+1, 2*popN):
        if 0<=newN<100001 and road[newN] == 0:
            road[newN] = road[popN] + 1
            path[newN] = popN
            queue.append(newN)

 

path배열에는 해당 인덱스에 도달하기 바로 직전 인덱스의 값을 저장해놓고 while문으로 path 배열의 값들을 불러와 최단경로를 출력하는 방식이다.

 

사실 아직도 위 풀이와 아래 풀이가 어떤 차이때문에 위는 시간초과가 나고 아래는 시간초과가 나지 않는것인지 잘 모르겠다..

조금 더 알아봐야겠다.

(혹시 아시는분 계시다면 댓글로 남겨주시면 감사하겠습니다!)

 

 

 

<핵심 정리>

1. BFS로도 최단 경로를 출력할 수 있다. path 배열을 만들고 해당 인덱스에 도달하기 직전 인덱스 값을 넣어 저장하면 된다.