[백준] 13549 숨바꼭질3 (BFS) - Python

 

13549번: 숨바꼭질 3

 

- 문제 설명

• 수빈이가 동생과 숨바꼭질을 한다.
• 수빈이는 동생을 찾기위해 순간이동, 앞으로 한칸이동, 뒤로 한칸이동이 가능한다.
• 순간이동은 0초, 앞뒤로 한칸이동은 1초가 걸린다.
• 수빈이가 동생을 찾을 수 있는 가장 빠른 시간은 몇초후인가?

 

- 접근방법

• BFS방식으로 순간이동 하는경우, 앞뒤로 이동하는 경우를 모두 탐색하자
• 순간이동은 뒤로는 할수 없다. 만약 수빈이가 동생보다 앞에있다면 뒤로가기로만 찾을 수 있으므로
  수빈이와 동생사이의 거리만큼 시간이 걸린다.
• 최초엔 방문처리를 해주지않고 모든 경우를 탐색하였더니 메모리 초과가 발생하였다.
• 먼저 방문했다면 그 방문이 순간이동을 이용했던 더 빠른 방문이므로
  더이상 탐색하지 않는다.
• BFS를 진행할때 순간이동은 0초가 걸리므로 큐의 제일 앞에 추가해서
  모든 순간이동을 탐색한 후 앞 뒤의 이동을 탐색한다.

 

- 입출력 예시

 

- 코드

from collections import deque

n, m = map(int, input().split())
MAX = 100001        # 문제에서 주어진 max값 = 100000
check = [0] * MAX   # check리스트를 만들어 탐색했던 곳 재탐색 방지
check[n] = 1        # 입력위치 방문처리
dq = deque()
dq.append((n, 0))   # 큐에 현재위치와 시간(0초) 추가

# 만약 수빈이가 동생보다 앞이라면 n - m 출력
if n >= m:
    print(n - m)
else:
    while dq:
        # 위치와 시간을 꺼냄
        x, y = dq.popleft()
        # 동생을 찾았다면 시간을 출력하고 반복탈출
        if x == m:
            print(y)
            break
        # 순간이동 한 값이 max보다 작고 방문한적 없다면
        if x*2 <= MAX-1 and check[x*2] == 0:
            # 순간이동은 0초가 걸리므로 먼저 처리하도록 큐의 앞에 추가
            dq.appendleft((x*2,y))
            check[x*2] = 1
        # 앞으로 한칸 이동한 값이 max보다 작고 방문한적 없다면
        if x+1 <= MAX-1 and check[x+1] == 0:
            dq.append((x + 1, y+1))
            check[x+1] = 1
        # 뒤로 한칸 이동한 값이 0보다 크고 방문한적 없다면
        if 0 <= x-1 and check[x-1] == 0:
            dq.append((x - 1, y+1))
            check[x-1] = 1