문제

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

소스코드

import sys
from collections import deque
input = sys.stdin.readline

#최단거리와, 최단거리를 만족하는 경우의 수를 구해야함 > 결과값을 담을 자료구조 2개 있어야함
if __name__ == "__main__":  
    n,k = map(int,input().split())
    visited = [[-1,0] for _ in range(100001)] #걸리는 시간, 경우의 수 
    q = deque()
    q.append(n) #n부터 시작
    visited[n][0] = 0 #n 일 때 0시간 ~ 
    visited[n][1] = 1 # 경우의 수 1가지 부터 시작

    while q:
        x  = q.popleft()
        for i in [x-1,x+1,x*2]:
            if 0 <= i < 100001:
                if visited[i][0] == -1: #방문 안한 경우
                    visited[i][0] = visited[x][0] + 1 #이전꺼에 +1 시간
                    visited[i][1] = visited[x][1] #동일한 경우의 수
                    q.append(i)                   
                elif visited[i][0] == visited[x][0] + 1: #걸리는 시간이 이전꺼에서 현재로 온거랑 지금이랑 같은 경우
                    visited[i][1] += visited[x][1] #경우의 수 더해주기, 그리고 더이상 탐색할 필요 없음;;

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

설명

최단거리를 찾는 문제이므로 BFS를 이용한다.
문제에 최단거리와, 최단거리를 만족하는 방법의 가짓수를 함께 출력하라고 했다. 그러면 최단거리와 가짓수를 저장할 자료구조가 2가지가 필요하다.
visited를 2차원으로 선언해서 0번째는 최단거리를 구하기 위한 시간으로 1번째값은 해당 인덱스에 도착했을 때 0번째 시간과 같은 경우의 수를 체크하도록 선언하였다.

• 방문을 하지 않은 경우엔 이전 인덱스 값에 + 1 한 시간을 주고 경우의 수는 쭉 이어나가 이전 인덱스의 경우의 수를 주고 탐색을 계속한다.
• 방문을 하고 이전 시간에 + 1 한 값이 현재 탐색하는 인덱스의 시간과 같다면 경우의 수를 모두 더하고 탐색을 더 이상 하지 않는다.

후기

최단거리와 경우의 수를 둘다 메모이제이션해야 비교를 하며 체크해줄 수 있다. 구할 값을 메모이제이션하자.