1697_숨바꼭질

입력

첫번 째줄에 순서대로 1차원에서의 시작 점과 도착 점이 주어짐

출력

시작 점에서 도착 점까지 도달하는데 필요한 최소한의 거리를 출력

조건

• 시작 점과 도착 점의 범위는 0 ~ 100,000
• 시작 점과 도착 점의 대소 관계는 정해져있지 않음(시작 점이 도착 점 기준으로 왼쪽 혹은 오른쪽에 위치)

풀이

시작 점에서부터 도착 점까지의 최소 거리를 구하면 되기 때문에 큐를 활용하여 bfs 재귀

1. 큐를 collections.deque 모듈을 사용하여 생성 후 [시작 점, 0(현재 소모한 거리)]로 초기화
   방문한 좌표들을 확인하기 위한 visited 배열 생성

q = deque([[N, 0]])
visited = [0 for _ in range(100001)]

2. 큐의 크기가 0이 될 때까지 while 문 실행
   큐를 popleft하면서 너비 우선 탐색
   - 참조하고 있는 좌표가 도착 점과 일치할 경우 현재 소모한 거리(cnt) return
   - 참고하고 있는 좌표가 0 미만, 100,000 초과일 경우 continue
   - 참고하고 있는 좌표가 0일 경우 0x2=0이기 때문에 x+1만 append, 이외의 경우는 3가지 경우(x+1, x*2, x-1) append
   

def bfs():
    global M, q
    
    while q:
        top_ = q.popleft()
        x, cnt = top_[0], top_[1]

        if x == M: return cnt

        if x < 0 or x > 100000: continue

        if visited[x] == 0:
            visited[x] = 1
            if x == 0: q.append([x+1, cnt+1])
            else:
                q.append([x+1, cnt+1])
                q.append([x*2, cnt+1])
                q.append([x-1, cnt+1])

    return -1

---

처음에는 큐를 배열로 선언하여 pop(0)으로 구현하였는데 처리 시간이 너무 많이 나왔다. 큐를 deque로 구현하여 처리 시간을 많이 단축 가능하였다.
큐는 deque로 구현하자.

전체 코드

숨바꼭질