[백준/파이썬] 13913번 숨바꼭질 4

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

13913번: 숨바꼭질 4

---

문제 & 테스트 케이스

---

문제 해석

1. 수빈이와 동생의 좌표가 주어진다.

2. 수빈이는 동생의 좌표로 이동해야한다.

3. 수빈이의 이동 방법은 -1, +1, *2 총 3가지 이며 모두 1초가 소요된다.

4. 동생을 잡는 최소 시간과 경로를 구하는 문제.

---

코드

from collections import deque

n, k = map(int, input().split())

# 이동 규칙 3가지
def move(dir, now):
    if dir == 0:
        return now - 1
    if dir == 1:
        return now + 1
    if dir == 2:
        return now * 2

# [이전 좌표]
visit = [-1] * (100001)

def dfs(now):
    q = deque()
    q.append((now, 0))  # 현재 위치, 현재까지 이동시간
    visit[now] = 0
    
    while q:
        now, cnt = q.popleft()
        
        if now == k:    # 가장 빠르게 도달하면
            print(cnt)  # 시간 출력
            route = ""  # 이동 경로를 visit 배열을 통해 구함
            for _ in range(cnt + 1):
                route = str(now) + " " + route
                now = visit[now]
            print(route)
            exit()
                
        for dir in range(3):
            next = move(dir, now)
            
            if not (0 <= next < 100001): continue
            if visit[next] == -1:
                visit[next] = now   # visit엔 이전 위치 좌표를 기록
                q.append((next, cnt + 1))

dfs(n)

---

문제 풀이

BFS큐를 통해 해결하되, 방문을 체크하는 visit 배열에 이전 좌표를 기록해 놓았다.

 

즉, 예제에서 5 4 8 16 17 의 경로로 이동하는데

visit[5] = 0, visit[4] = 5, visit[8] = 4, ... 이처럼 저장해두었다.

 

이후 동생의 좌표에 도달하면 visit 배열을 타고 거꾸로 넘어가 이동 경로를 구해주는 방식으로 문제를 해결하면 된다.