[백준] 1697 - 숨바꼭질(BFS) - (python 파이썬)

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

1697번: 숨바꼭질

 

풀이과정 :

처음에는 동적프로그래밍으로 접근해보다가 빙빙 돌다가,, BFS 알고리즘임을 알게되었고,

BFS를 다시 공부하고 풀었다. 가장 기본적인 BFS 문제이며, 파이쎁 같은 경우 BFS는 양쪽

입출력이 모두 가능한 덱으로 구현해야한다. 코드리뷰를 하자면, 범위 값을 잡아주고

범위 안의 방문처리 리스트(몇번 이동이 있었는지)를 만들어준다. 그 뒤로 덱의 왼쪽

인자를 출력해주면서 그것이 K의 위치와 같은지 계속해서 확인해주고,

X-1, X+1, X*2 로 차례로 이동해주면서 최단거리를 구하는 알고리즘을 구현하면된다.

 

from collections import deque

def bfs(N, K):
    dq = deque()
    dq.append(N)
    while dq:
        temp = dq.popleft()
        if K == temp:
            print(dlst[temp])
            break
        for i in (temp-1, temp+1, temp*2):
            if 0<= i <= MAX and not dlst[i]: #범위내의 이동이면서, 처음방문하는곳에 한하여
                dlst[i] = dlst[temp] + 1
                dq.append(i)

MAX = 100000
N, K = map(int, input().split())
dlst = [0] * (MAX+1) #방문처리 리스트
bfs(N, K)

 

답(이미지)

 

후기 : BFS를 학교수업 때 이후로 처음 만나서 이해하는데 다소 시간이 걸렸다.