숨박꼭질 2 - 골드 4 (백준, BFS)

def bfs(start):
    global result
    q = deque()
    q.append(start)
    arr[start] = 0
    while q:
        x = q.popleft()
        if x == K:
            result += 1
            continue
        for nx in (x*2, x+1, x-1):
        	# 최소시간이 arr[K]에 이미 있는 경우에는 같을 때도
            # q.append해서 result가 증가될 수 있도록
            if 0 <= nx < 100001 and (arr[nx] == arr[x] + 1 or arr[nx] == -1):
                arr[nx] = arr[x] + 1
                q.append(nx)


N, K = map(int, input().split())
arr = [-1] * 100001
result = 0

bfs(N)

print(arr[K])
print(result)

 

1. q가 빌때까지 x+1, x-1, x*2로 이동을 반복을 한다. (우선순위를 x*2로 두었다)

  - arr[nx]에 이전시간+1 을 해주고 q에 append (첫 방문이거나 시간이 같은 경우)

  - x가 동생의 위치(K)이면 result += 1 (가능한 경우의 수 1증가)

2. 최소 시간과 경우의 수 출력

 

BFS로 3 가지 이동 방법을 모두 사용하여 가능한 경우의 수를 추론해내는 방식이다.