[백준12851&파이썬] BFS를 이용해 최단시간 도착과 최단시간의 모든경우의 수를 구하자

# 문제

백준12851 숨바꼭질2 파이썬 풀이

12851번: 숨바꼭질 2

# 코드

import sys
from collections import deque
from collections import defaultdict

N, K = map(int, sys.stdin.readline().split())

dirs = [
  -1, 1
  ]

visit = [False] * (100_001)
visit[N] = True
dq = deque()
dq.append((N, 0))
counter = defaultdict(int)

cnt = 0
minimum_step = -1
while len(dq) != 0:
  pos, step = dq.popleft()
  visit[pos] = True

  if pos == K :
    counter[step] += 1

  # 곱하기로 이동할 경우
  next = pos * 2
  if 0 <= next <= 100_000 and visit[next] == False:
    dq.append((next, step + 1))

  # -1 또는 +1로 이동하는 경우
  for dir in dirs:
    next = pos + dir
    if 0 <= next <= 100_000 and visit[next] == False:  # 방문 가능하는 곳이면 방문시킨다.
      dq.append((next, step + 1))

# 최단거리기이기 때문에 counter가 맨앞일 경우임
for item in counter.items() :
  print(item[0])
  print(item[1])
  exit()

 

# 풀이

• 문제가 요구하는 것은, 최단도착시간을 구하는 것과 최단 도착시간으로 도착하는 모든 경우의 수를 구하는 것이다.
• 내가 푼 풀이는 최단도착시간을 구하고. 모든 도착의 경우의 수를 구하는 풀이다.
• 모든 도착의 경우는 dict을 이용해서 풀었다. 해당 step에 도착했다면 추가해주고, 최종 출력에는 가장 작은 step과 가지수를 출력했다.
• 조금은 비효율적인 풀이다. 내가 생각했던 것. 도착점까지 구한다음에, 구해지면 구해진 step까지만 큐에 관리하고 큐를 끝내버린다.
• 그다음에 큐에서 뺴기만하면서 k와 같은지를 카운팅하는 것으로 조금 개선하면 좋을 듯 했다.

# 참고

조금 잡기술인데, 항상 *2같은 연산은ㅇ ㅓ떻게 처리해야하는지 의아했는데 아래와 같이 처리가 가능할듯으로 보인다.

while deq:
    x = deq.popleft()

    for nx in (x*2, x+1, x+-1):
        if 0<= nx <= 100000:
            if visited[nx][0] == -1:
            	pass