[python]백준 12851번: 숨바꼭질 2(BFS)

# 12851 숨바꼭질 2

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

12851번: 숨바꼭질 2

코드

from collections import deque

n, k = map(int, input().split())
visited = [0] * 100001

q = deque([(n, 0)])
fast, way = 10 ** 6, 0

while q:
  now, time = q.popleft()
  visited[now] = 1
  if now == k and time <= fast:
    fast = min(fast, time)
    way += 1
  if time > fast: break

  for x in (now - 1, now + 1, now * 2):
    if x in range(100001) and not visited[x]:
      q.append((x, time + 1))
  
print(fast)
print(way)

📝 풀이

수빈이가 동생을 찾을 때 2가지 방법으로 찾을 수 있다.

첫번째 걷는 방법: 1초 후 x-1 or x+1

두번째 순간이동: 1초 후 2*x로 이동

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구해야 한다.

🔓 코드 뜯어보기

from collections import deque

n, k = map(int, input().split())
visited = [0] * 100001

q = deque([(n, 0)])
fast, way = 1e9, 0

수빈이의 위치 n과 동생의 위치 k를 각각 저장해주고, 문제 범위에 해당하는 visited 리스트를 생성해준다. 가장 빠른 시간을 구해야 하므로 min값으로 구분할 수 있게 fast에 1e9값을 넣어준다.

while q:
  now, time = q.popleft()
  visited[now] = 1 # 여기서 방문 처리를 함
  if now == k and time <= fast:
    fast = min(fast, time)
    way += 1 
  if time > fast: break # 큐에는 시간 순으로 들어가므로 fast보다 커지면 탐색을 종료

  for x in (now - 1, now + 1, now * 2):
    if x in range(100001) and not visited[x]:
      q.append((x, time + 1))
  
print(fast)
print(way)

q가 없을때까지 while문을 실행시켜주고 q에 저장된 위치 값과 시간을 now와 time에 저장시켜준다.

visited를 큐에 넣을 때가 아닌 큐에서 꺼낼 때 처리하는 이유는 큐에 넣을 때 방문 처리를 하게 되면 동생을 찾을 수 있는 여러 가지가 있음에도 불구하고 최초의 발견 이후로는 방문처리가 되어 있어 아예 큐에 넣지 않게 된다.

 

큐에서 꺼냈을 때 방문 처리를 하게 되면 일단 큐에는 들어갈 수 있기 때문에 여러 가지 경우를 셀 수 있게 된다.

BFS에서는 Queue를 사용하고, 큐는 선입선출 구조이다. 우리는 큐에 값을 넣을 때 현재 숫자와 시간을 넣는다. 시간은 점차 증가하는 방향으로 넣게 되는데 그 말은 즉 큐에서 데이터를 꺼낼 때 시간이 줄어드는 경우는 없다는 것이다.

그래서 큐에서 뽑은 time이 fastest보다 커지면 더 이상 최소 시간에서 찾을 수 없다는 것이기 때문에 break로 탐색을 종료한다.

 

if now == k and time <= fast 현재위치가 k이거나 fast가 time보다 작으면 fast에 fast와 time중 작은 값을 넣어주고 way를 증가시켜준다.

반복문을 통해서 현재위치에서 -1, +1, *2를 해주어서 모든 경우의 수를 입력해주고 x가 범위내에 있거나 방문하지 않았다면 q에 x값과 시간 +1을 넣어준다.

 

참고

https://latte-is-horse.tistory.com/338