[백준] 12851 숨바꼭질 2 in Python : bfs의 응용

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

12851번: 숨바꼭질 2

 

bfs로 풀기 위해서, 100001개의 공간이 필요하다 이 개수는 문제에서 주어진 노드의 범위(0<= n,k <= 100000)이다. 

visited = [[-1, 0] for _ in range(100001)] # (cost , 방법의 개수)

각 노드에 대해 최소 비용도 구해야하고, 최소비용으로 가는 경우 방법을 카운트 해주어야 하기 때문이다 

for 문으로 간단히 갈 수 있는 이동 방법의 경우를 체크한다 !! 

for i in [now-1, now+1, now*2]:

처음으로 방문하는 경우와 이미 방문한 적 있는 경우 2가지로 나누어서 생각한다. 

i) 처음으로 방문하는 경우 

if visited[i][0] == -1: # 첫 방문

 

ii) 이미 현재 노드를 방문한 적 있는 경우 

elif visited[i][0] == visited[now][0] + 1: # 이미 방문했다면, 최단거리인 경우에만 갱신함

최단거리인 경우에만 방법의 수를 업데이트 해준다. (더해준다)

visited[i][1] += visited[now][1] # i 까지 가는 방법의 수 갱신 !

 

# 12851
from collections import deque
n, k = map(int, input().split())

visited = [[-1, 0] for _ in range(100001)] # (cost , 방법의 개수)

def bfs():
    q = deque()
    q.append(n) # start node 는 n
    visited[n][0] = 0
    visited[n][1] = 1

    while q:
        now = q.popleft()
        for i in [now-1, now+1, now*2]:
            if 0 <= i <= 100000: # 주어진 범위
                if visited[i][0] == -1: # 첫 방문
                    visited[i][0] = visited[now][0] + 1
                    visited[i][1] = visited[now][1] # 방법의 개수
                    q.append(i)

                elif visited[i][0] == visited[now][0] + 1: # 이미 방문했다면, 최단거리인 경우에만 갱신함
                    visited[i][1] += visited[now][1]

bfs()

print(visited[k][0])
print(visited[k][1])