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

문제: www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

import sys
from collections import deque
N,M = map(int,input().split())
loc=[sys.maxsize]*100001
loc[N]=0
li=[]
def bfs(n):
    q=deque()
    cnt=0
    q.append([n,cnt])
    while q:
        a=q.popleft()
        if a[0]==M:
            print(a[1])
            li.append(a[0])
            while loc[li[-1]]!=0:
                if li[-1]-1>=0 and loc[li[-1]]-1==loc[li[-1]-1]:
                    li.append(li[-1]-1)
                elif li[-1]+1<100000 and loc[li[-1]]-1==loc[li[-1]+1]:
                    li.append(li[-1]+1)
                elif li[-1]%2==0 and loc[li[-1]]-1==loc[li[-1]//2]:
                    li.append(li[-1]//2)
            li.reverse()
            print(' '.join(map(str,li)))
            break
        if a[0]-1>=0:
            if a[1]+1<loc[a[0]-1]:
                loc[a[0]-1]=a[1]+1
                q.append([a[0]-1,a[1]+1])
        if a[0]*2<=100000 and M*2>a[0]*2:
            if a[1]+1<loc[a[0]*2]:
                loc[a[0]*2]=a[1]+1
                q.append([a[0]*2,a[1]+1])
        if a[0]+1<=100000:
            if a[1]+1<loc[a[0]+1]:
                loc[a[0]+1]=a[1]+1
                q.append([a[0]+1,a[1]+1])
        
 
bfs(N)
 

위의 코드는 시간초과가 난 코드다.

시간초과가 난 이유는 해당 값을 찾고나서 역 추적하여 찾는 과정에서 시간초과가 난 것 같다.

고민을 해봤지만 도저히 생각이 나질 않아서 다른 분의 코드를 참고했다.

 

 

import sys
from collections import deque
def solve(visited,n,k):
    queue=deque()
    queue.append(n)
    while queue:
        x=queue.popleft()
 
        if x==k:
            #이동하는데 걸리는 최소시간
            print(visited[x])
            #이동한방법은 이동경로를 역순으로 출력
            p=[]
            #p에다가 마지막경로인 x를 넣고
            #x에다가 다시 path에 저장해둔 이전의 좌표 넣기
            #x가 시작점과 같아질때까지 반복
            while x!=n:
                p.append(x)
                x=path[x]
            #while문이 n일때 나가니깐 n은 추가해주기
            p.append(n)
            p.reverse()
            print(' '.join(map(str,p)))
            return
 
        for nx in (x+1,x-1,x*2):
            if 0<=nx<100001 and visited[nx]==0:
                visited[nx]=visited[x]+1
                #path[다음좌표]=현재좌표
                path[nx]=x
                queue.append(nx)
 
n,k=map(int,input().split())
visited=[0]*100001
path=[0]*100001
solve(visited,n,k)

참고:https://sinsomi.tistory.com/entry/%EB%B0%B1%EC%A4%80-Python-13913%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-4-%EC%B4%88%EC%BD%94%EB%8D%94

[백준 / Python] 13913번 숨바꼭질 4 | 초코더

풀이 접근법은 visited와 path를 둔 다음에 visited는 최소시간을 계산하는 데 이용하고 path는 경로를 찾는데 이용한다.

이때 path는 이전 방문위치를 저장한다. 그러면 이제 계속 역추적하다 보면 n까지 도달한다. 하지만 위의 코드에서 while은 n이 아닐때까지 이므로 그 다음줄에 n을 추가해준다. 그리고 뒤에서 앞으로 저장되어 있으므로 reverse를 이용하여 정렬하면 답을 찾을 수 있다.