[BOJ] 숨박꼭질 4 R

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

 

 

 

1. 문제 이해 및 해결과정

- 최적의 이동경로까지 출력해야한다.  - path[다음위치] = cur(현재) , path에 방문했던 위치를 저장한다.  - k에 도착하면 backtracking 해서 출발위치까지 p 에 최적 이동경로를 저장한다.  - p는 backtracking 한 것이므로 출발위치 추가해서 reverse해야한다.

-

 if cur==k:
        print(time[cur])
        p=[]
        print(path)
        while cur!=n:
            p.append(cur)
            cur=path[cur]
        print(p)

윗 줄은 path , 아래줄은 p 

2. 풀이방법

 1. BFS

#숨바꼭질4
#https://www.acmicpc.net/problem/13913
import sys
from collections import deque
sys.stdin = open("input.txt","r")
input=sys.stdin.readline

n,k=map(int,input().split())
MAX=100000
time = [0]*(MAX+1)
path = [0]*(MAX+1)
Q=deque()
Q.append(n)
while Q:
    cur=Q.popleft()
    if cur==k:
        print(time[cur])
        p=[]
        print(path)
        while cur!=n:
            p.append(cur)
            cur=path[cur]
        print(p)
        p.append(n)
        p.reverse()
        print(' '.join(map(str,p)))
        break
    for next in (cur-1,cur+1,cur*2):
        if 0<=next<=MAX and time[next]==0:
            time[next]=time[cur]+1
            path[next]=cur
            Q.append(next)

 

3. 오답원인

 

4. 알게된 점