[Python][백준] 13913번 숨바꼭질 4

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

공부 날짜 : 2023.02.07
정답 참조 여부 : X

출발위치와 결과위치가 주어질 때, 결과위치까지의 최단거리와 경로를 출력하는 문제이다.

---

문제만 처음 읽었을 때는 좀 당황했다.

이제까지 BFS를 구현할 때 항상 거리만 구해왔기 때문에, 실제 경로를 구하는건 처음이었고, 무엇보다 경로가 여러개인 경우가 있을텐데 중복 정답을 허용을 하나 싶었다.

2번째 문제인 중복정답의 경우는 예제 입력이 중복인 케이스라서 신경쓰지않고 일단 구현했다.

경로를 직접적으로 구하는 경우에는 탐색여부를 저장할 때 최단거리로 도달한 경로의 이전 칸을 저장했다.

말로 쓰니 좀 헷갈릴 수 있는데,

depue.append((x+1, x, dis+1))

~~
 x, back_x, dis = deque.popleft()
 	# 초기값은 -1, 100001
    if visited[x][1] > dis:
        visited[x] = (back_x, dis)

이런식으로 방문해야할 위치를 저장할 때 방문위치, 현재위치, 거리를 저장해 주었다.

그 다음 방문 처리할 때 visited에 저장된 dis가(경로가) 현재 dis보다 길다면 이전 노드로 갱신해 주었다. 또한, 초기값을 (-1, 100001)으로 저장하여 방문하지 않았으면(-1) 현재 경로가 더 짧아서 저장되게해 주었다.

소스코드

import sys
input = sys.stdin.readline
from collections import deque
#############################################
n, k = map(int, input().split())

# 시작점과 거리를 초기값으로 저장
visit = deque()
visit.append((n, n, 0))

# 방문 여부를 판단하는 배열
# [0]은 이전에 방문한 칸, [1]은 거리
visited = [(-1, 100001) for _ in range(100001)]

# 정답이 저장될 두 변수
ans_dis = 100001
# ans_count = 0

# 다음 탐색한 장소가 있을 때 순환
while visit:
    x, back_x, dis = visit.popleft()
    # 현재 도달 방식이 현재 저장된 방법보다 최단 거리면, 이전 위치와 거리 저장
    # 초기값은 -1, 100001
    if visited[x][1] > dis:
        visited[x] = (back_x, dis)


    # 목적지 탐색 시 거리와 개수 +1
    if x == k and ans_dis > dis:
        ans_dis = dis
        break

    # 현재 장소에서 이동가능하고, 이전에 방문하지 않은 모든 칸 추가
    # 이동가능한 칸과 현재칸, 거리 +1해서 추가
    if 0 <= x+1 <= 100000 and visited[x+1][0] == -1:
        visit.append((x+1, x, dis+1))

    if 0 <= x-1 <= 100000 and visited[x-1][0] == -1:
        visit.append((x-1, x, dis+1))

    if x < k and 0 <= x*2 <= 100000 and visited[x*2][0] == -1:
        visit.append((x*2, x, dis+1))

print(ans_dis)

ans_path = deque()
while True:
    if n == x:
        ans_path.appendleft(n)
        break

    ans_path.appendleft(x)
    x = visited[x][0]

print(*ans_path)