BOJ - 숨바꼭질3 13549번 (python)

❓ 문제 - 백준 숨바꼭질3 13549번 - python 풀이법

출처 

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

13549번: 숨바꼭질 3

 

 

📝 문제해결법

1. 이 문제는 그래프탐색(BFS)와 DP를 활용하여 풀었다.

• 일단 모든 숫자 범위(0 <= N, K <= 100,000) 안에서 해당 인덱스를 방문하기까지 걸리는 시간의 최대값을 100001로 셋팅하고, BFS를 돌면서 visited 리스트에서 해당 인덱스를 방문했을 때까지 걸리는 시간의 최솟값을 계속 갱신
• 이동하는 시간 time이 k까지 도달하는 시간(time_max)보다 크다면 continue 해줘서 다른 위치의 방문을 중지 
• 현재 위치 x(now 변수 사용)에서 +1, -1 로 이동했을 때는 time 을 +1 증가하게 하며, 현재위치 x에서 순간이동 했을 때는 time을 그대로 하고 이동했을 때 범위(0 이상 100,000이하)에서 이동하는 데 걸리는 시간의 최솟값을 갱신하고 q에 넣어줌
• 또한 이동하다가 k에 도달했을 때, time_max 즉, k까지 이동하는데 걸리는 시간을 최솟값으로 계속 갱신

 

 

💻 소스코드

# 숨바꼭질3 - BOJ 13549
# BFS + DP

import sys
from collections import deque

input = sys.stdin.readline
n, k = map(int, input().split())
dx =[1, -1]

visited = [100000 for _ in range(100001)]
time_max = 100000
def bfs(start, end):
    global time_max
    q = deque()
    q.append((start, 0))
    visited[start] = 0
    while q:
        now, time = q.popleft()
        if time >= time_max:
            continue
        for i in range(3):
            if i == 2:
                nx = 2 * now
                new_time = time
            else:
                nx = now + dx[i]
                new_time = time + 1

            if 0 <= nx <= 100000:
                if visited[nx] > new_time:
                    visited[nx] = new_time
                    q.append((nx, new_time))
                    if nx == k:
                        time_max = min(time_max, time)


bfs(n, k)
print(visited[k])