[Baekjoon] 숨바꼭질 4(python)

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

문제 접근

BFS를 이용하여 목적지에 도달할 때까지 계속해서 탐색하는 방식으로 문제를 접근했다.

 

무조건 current - 1, current + 1, current * 2에 해당하는 좌표와 지금까지의 경로를 같이 큐에 삽입하도록 했는데 메모리 초과가 발생했다.

 

이미 방문한 위치를 또 방문할 뿐더러 중복되는 모든 경로까지 큐에 삽입하게 되기 때문이다.

 

따라서 dist배열을 통해 이미 방문한 위치를 체크하면서 해당 위치까지 도달하는데 걸리는 시간을 같이 저장했다.

 

또 경로를 트래킹하기 위해서 foot_print배열에 해당 위치에 이전 위치를 저장하도록 문제를 해결했다.

 

틀린 코드

...

def bfs():
    q = deque()
    q.append([N, [N]])

    while q:
        current, route = q.popleft()

        if current == K:
            return route

        q.append([current - 1, route + [current - 1]])
        q.append([current + 1, route + [current + 1]])
        q.append([current * 2, route + [current * 2]])

...

---

풀이 과정

1. BFS를 통한 목적지 탐색

BFS를 통해 목적지까지 탐색하면서 도달하는 위치에 depth를 저장하고 이전 위치를 경로로 저장한다.

def bfs():
    q = deque()
    q.append(N)

    while q:
        x = q.popleft()

        if x == K:
            path(x)
            break

        for nx in [x - 1, x + 1, x * 2]:
            if 0 <= nx < 100001 and dist[nx] == 0:
                foot_print[nx] = x
                dist[nx] = dist[x] + 1
                q.append(nx)

 

2. 경로 구하기

목적지에서 시작하여 foot_print를 추적하여 경로를 구한다. 목적지까지 도달하기까지 걸린 시간만큼만 추적하면 경로를 추적할 수 있다.

def path(x):
    result = []

    for _ in range(dist[x] + 1):
        result.append(x)
        x = foot_print[x]

    print(len(result) - 1)
    print(*result[::-1])

---

정답 코드

"""
    백준 13913번 숨바꼭질 4
"""

import sys

from collections import deque


def path(x):
    result = []

    for _ in range(dist[x] + 1):
        result.append(x)
        x = foot_print[x]

    print(len(result) - 1)
    print(*result[::-1])


def bfs():
    q = deque()
    q.append(N)

    while q:
        x = q.popleft()

        if x == K:
            path(x)
            break

        for nx in [x - 1, x + 1, x * 2]:
            if 0 <= nx < 100001 and dist[nx] == 0:
                foot_print[nx] = x
                dist[nx] = dist[x] + 1
                q.append(nx)


N, K = list(map(int, sys.stdin.readline().split()))
foot_print = [0] * 100001
dist = [0] * 100001

bfs()