[백준] 13549 숨바꼭질 3 파이썬

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

13549번: 숨바꼭질 3

 

dfs로 풀었더니 시간초과뜬다.

import sys
sys.setrecursionlimit(10**7)

a, b = map(int, input().split())

minTime = 100000


def dfs(curtime, curx, type):

    global b
    global a
    global minTime

    if curx <= 0:
        return
    if curx >= b:
        minTime = min(minTime, curtime + curx - b)
        print(minTime)
        return
    if curtime > minTime:
        return

    dfs(curtime, curx * 2, 0)  # 순간이동
    if type != 1:
        dfs(curtime + 1, curx - 1, -1)  # -1로 걸어갈 때
    if type != -1:
        dfs(curtime + 1, curx + 1, 1)  # +1로 걸어갈 때


dfs(0, a, 0)
print(minTime)

찾아본 결과 다익스트라 혹은 bfs로 풀어야한다길래 bfs로 바꾸었다.

 

그런데 처음엔 주석을 넣어놓은 부분에 appendleft 대신 append를 사용했다가 계속 틀렸었다.

순간이동은 시간이 걸리지 않기 때문에 큐에서 먼저 처리해줘야 맞는 답이었다.

아래 질문글을 참고했다.

https://www.acmicpc.net/board/view/73660

글 읽기 - 파이썬) 몇가지 질문이 있습니다

 

from collections import deque

a, b = map(int, input().split())

dist = [-1]*100001
q = deque()
q.append(a)
dist[a] = 0

while q:
    now = q.popleft()
    if now == b:
        print(dist[b])
        break
    if now*2 < 100001 and dist[now*2] == -1:
        q.appendleft(now*2) # 추가 시간이 발생하지 않으므로 큐에 먼저 넣어야함
        dist[now*2] = dist[now]
    if now+1 < 100001 and dist[now+1] == -1:
        q.append(now+1)
        dist[now+1] = dist[now]+1
    if now-1 >= 0 and dist[now-1] == -1:
        q.append(now-1)
        dist[now-1] = dist[now] + 1

 

2022.01.07 다시풀어봄

from collections import deque

n, k = map(int, input().split())
time = [-1]*100001

q = deque([(n, 0)])
time[n] = 0

while q:
    now, t = q.popleft()
    if now == k:
        print(time[now])
        break

    if 0 <= now*2 <= 100000 and (time[now*2] == -1 or time[now*2] > t):
        time[now*2] = t
        q.append((now*2, t))

    for i in (now-1, now+1):
        if 0 <= i < 100000 and (time[i] == -1 or time[i] > t+1):
            time[i] = t+1
            q.append((i, t+1))

bfs로 접근한 것은 맞았는데 t의 개념을 두 번 사용하고 (큐에 t를 저장할 필요 없었음)

문제에서 0 포함하였는데, 1부터인줄 알고 몇 번 틀렸었다.

그리고 순간이동할 때 appendleft를 사용하는 대신 조건문으로 시간이 더 적을 때는 다시 연산해 준 차이점이 있었다.

어쨌든 통과