[알고리즘] 백준13549 숨바꼭질3 - 파이썬

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

13549번: 숨바꼭질 3

 

 

 

[풀이 코드]

 

from collections import deque
n, k = map(int, input().split())
MAX = 100000
cnt_list = [0] * (MAX+1)
visited = [False] * (MAX+1)
visited[n] = True
def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == k:
            print(cnt_list[x])
            break

        for dx in [x*2, x-1, x+1]:
            if x*2 == dx and 0 <= dx <= MAX and not visited[dx]:
                queue.append(dx)
                cnt_list[dx] = cnt_list[x]
                visited[dx] = True

            if (dx-1==x or dx+1==x ) and 0 <= dx <= MAX and not visited[dx]:
                queue.append(dx)
                cnt_list[dx] = cnt_list[x] + 1
                visited[dx] = True

bfs()

• *2를 이동해야 하는 경우는 초가 지나지 않기 때문에 if문을 통해 +1, -1을 이동하는 경우와 나누어 처리하였다.