[백준] 13913 숨바꼭질 4 (python 파이썬)

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

13913번: 숨바꼭질 4

숨바꼭질 시리즈 마지막 숨바꼭질 1 먼저 풀어보는 게 좋다.

---

아이디어

1. bfs

• 큐에 x +1, x - 1, x * 2를 조건에 맞으면 추가해준다.
• 큐에 위치와 시간 그리고 지나온 길도 같이 넣어준다.
• 도착하면 도착 시간과 경로를 리턴 후 출력.

---

전체 코드

from collections import deque
N, K = map(int,input().split())
visited = [False] * (200001)

def bfs(n):

    deq = deque()
    deq.append([n, 0,[n]])
    visited[n] = True

    if n > K:
        return n - K, [int(x) for x in range(n,K - 1,-1)]


    while deq:
        x, count, road = deq.popleft()

        if x == K:
            return count, road

        arr = [x - 1, x + 1, x * 2]
        for a in arr:
            if 0 <= a <= 100000 and visited[a] == False:
                visited[a] = True
                r = road + [a]
                deq.append([a, count + 1, r])

ans_count, ans_road = bfs(N)

print(ans_count)
for path in ans_road:
    print(path,end=' ')

---

코드 설명

 

def bfs(n):

    deq = deque()
    deq.append([n, 0,[n]])
    visited[n] = True

    if n > K:
        return n - K, [int(x) for x in range(n,K - 1,-1)]


    while deq:
        x, count, road = deq.popleft()

        if x == K:
            return count, road

        arr = [x - 1, x + 1, x * 2]
        for a in arr:
            if 0 <= a <= 100000 and visited[a] == False:
                visited[a] = True
                r = road + [a]
                deq.append([a, count + 1, r])

기존 숨바꼭질 문제와 매우 유사하다. 우리가 할 건 경로만 같이 저장해주면 된다.

근데 그냥 이렇게 하면 100000 0 같은 입력이 들어오면 시간 초과가 뜬다.

 

이럴 때는 이미 N보다 K가 큰 경우 따로 생각해준다.

도착하려면 뒤로 가는 방법(x - 1)뿐이므로 시간은 N - K

경로는 N부터 K까지 1씩 감소하면 된다.