[BOJ/python]13549번 숨바꼭질 3

백준 13549번 숨바꼭질 3 파이썬 BFS

문제 링크 - https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

당연히 백트래킹이겠거니 생각하고 풀었다. 시간 초과에 재귀 오류까지 났지만 가지치기를 조금 더 효율적으로 바꾸는 시도만 계속해서 반복했다.

결국 BFS로 푸는 것을 보고 시도했다. 백트래킹을 항상 쓰려고 하면 안된다. 똑같은 지점에 방문하는 걸 처리하는 것이 까다롭기 때문이다.

1-1. 백트래킹 풀이(오답)

• 수빈이의 위치가 0 이 아니라면 순간 이동을 하는 재귀로 들어간다.
• 수빈이의 위치에서 +1만큼 이동하는 재귀로 들어간다.
• 재귀를 반복하며 수빈이의 위치 place가 동생의 위치 K보다 커지는 경우 재귀를 중지하고 place-K 시간을 더해준다(place-K 시간 동안 뒤로 이동하여 동생의 위치 도착)
• 재귀를 반복하며 수빈이의 위치 place가 동생의 위치 K가 되는 경우 재귀를 중지하고 정답을 갱신한다.
• 재귀를 반복하며 소요된 시간이 갱신된 정답보다 큰 경우 재귀를 중지한다.
• 재귀를 반복하며 수빈이의 위치가 주어진 범위를 벗어난 경우 재귀를 중지한다.

1-2. 백트래킹 코드(오답)

import sys
sys.setrecursionlimit(10**5)

N, K = map(int,input().split())
def DFS(place, time):
    global answer
    
    if time>=answer or place<0 or place>100000:
        return
    
    if place>K:
        answer = min(answer, time+ place-K)
        return 
    
    if place == K :
        answer = min(answer, time)
        return
    if place!=0:
        DFS(place*2, time)
    
    DFS(place+1, time+1)

if K<N :
    answer = N-K
else:
    answer = K-N
    DFS(N,0)
    
print(answer)

2-1. BFS 풀이

• 방문 배열에 소요된 시간을 저장한다.
• BFS를 진행하며 다음 위치에 가기 위해 방문 배열에 저장된 시간보다 짧게 걸린다면 queue에 넣는다.

2-2. BFS 코드

from collections import deque

N,K = map(int, input().split())
q=deque()
q.append([N,0])

visited=[float('inf') for _ in range(100001)]
visited[N]=0

if K<N :
    answer = N-K
else:
    answer = K-N
    while q:
        place, time = q.popleft()
        
        if place>=K :
            answer = min(answer, place-K+time)        
            continue
        
        if time>=answer:
            continue        
        
        for next_place, next_time in ([place*2, time],[place+1, time+1],[place-1, time+1]):
            if 0<=next_place<100001 and visited[next_place] > next_time:
                visited[next_place] = next_time
                q.append([next_place, next_time])

print(answer)