숨바꼭질2[백준 12851] - python

방문한 곳의 최소 시간과 방법의 수를 출력해주어야 한다.

각 지점마다 두개의 정보를 가지고 있어야 하므로 이차원 배열로 선언해 주었다.

 

정답 코드 먼저 살펴보자

n, k = map(int, input().split())
MAX_LENGTH = 100001
visited = [[-1, 0] for _ in range(MAX_LENGTH)]

queue = []
queue.append(n)
# 처음 방문한 곳은 방문정보와 방법의 수를 업데이트
visited[n][0] = 0
visited[n][1] = 1

while queue :
  x = queue.pop(0)
  
  for i in [x-1, x+1, x*2] :
    if 0 <= i <= 100000 :
      # 방문한적이 없는 애들만 q에 넣어주자
      # 제일 처음 방문한 친구가 가장 최단 시간에 방문한 것일 거다.
      if visited[i][0] == -1 :
        visited[i][0] = visited[x][0] + 1
        visited[i][1] = visited[x][1]
        queue.append(i)
      
      # 방문한적이 있고 바로 다음 방문할 예정이라면
      # 방문예정인 곳의 방법의 수는 이전 스팟의 방법의 수를 더해주어야 한다.
      elif visited[i][0] == visited[x][0] + 1 :
        visited[i][1] += visited[x][1]

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

 

방법의 수를 같이 출력해주어야 해서 까다로웠던 문제로 기억 하고 있다.

최단시간은 이전에 방문한 적이 없을 경우에만 업데이트 해주었고

방법의 수는 최단 시간을 가리지 않으므로 이후 방문할 곳의 시간이 현재 + 1 이라면 방법의 수에 더해주었다.

 

 

 

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

12851번: 숨바꼭질 2

 

출처: https://velog.io/@dhelee/%EB%B0%B1%EC%A4%80-12851%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%884-Python-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS