[백준] 12851번 숨바꼭질 2 (bfs, 파이썬)

 

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

1. 아직 완전히 이해하지는 못했는데 cnt는 방법의 수이고 check는 현재위치에서 걸린 시간이다 

y는 x에서 이동할 수 있는 곳을 나타내는데 y의 시간이 x에서 한 번 이동하게 되는 시간이랑 같거나 처음 방문한다면 

경우의 수를 더해주기 위해 큐에 넣어주면 된다.

from collections import deque

N, K = map(int, input().split())
MAX_SIZE = 100001

q = deque()
q.append(N)

cnt=0
check=[-1]* MAX_SIZE
check[N]=0
while q:
    x = q.popleft()
    if x==K:
        cnt+=1
    for y in [x * 2, x + 1, x - 1]:
        if 0 <= y < MAX_SIZE:
            if check[y]==-1 or check[y]==check[x]+1: #시간: 방문한 적 없거나 현재시간 +1인경우
                check[y]=check[x]+1
                q.append(y)

print(check[K])
print(cnt)

2. 다시 풀어봤는데 check[y] >= check[x]+1 인 순간에 업데이트 해주면 최단시간으로 업데이트 해준다.

check[y]>check[x]+1 이 아닌 이유는 같은 방법의 수를 증가시켜줘야 되기 때문에 다시 큐에 넣어줘어야 되서이다. 

from collections import deque

N, K = map(int, input().split())
MAX_SIZE = 100001

q = deque()
q.append(N)

cnt=0
check=[-1]* MAX_SIZE
check[N]=0
while q:
    x = q.popleft()
    if x==K:
        cnt+=1
    for y in [x * 2, x + 1, x - 1]:
        if 0 <= y < MAX_SIZE:
            if check[y]==-1 or check[y]>=check[x]+1: #시간: 방문한 적 없거나 현재시간 +1인경우
                check[y]=check[x]+1
                q.append(y)

print(check[K])
print(cnt)