코드

from collections import deque

n, k = map(int, input().split())

max_range = 100001

# visisted[방문 소요 시간][경우의 수]
visited = [[0, 0] for _ in range(max_range)]

def bfs(n):
    q = deque()
    q.append(n)
    
    visited[n][0] = 1 # 시작은 방문 처리
    visited[n][1] = 1 # 기본 적으로 1개의 경우의 수가 존재하므로 시작을 1로 잡음
    
    while q:
        x = q.popleft()
        
        # 찾으면 함수 종료
        if x == k:
            return
        
        for i in (x-1, x+1, x*2):
            if i < 0 or i >= max_range:
                continue
                
            # 처음 방문하는 점인 경우
            if visited[i][0] == 0:
                
                # 이전 까지의 소요 시간에 +1
                visited[i][0] = visited[x][0] + 1
                
                # 첫 방문이므로 이동하기 전과 후 모두 하나의 경우에서 발생하는 일
                # 따라서 이전 좌표까지의 경우의 수를 그대로 받아옴
                visited[i][1] = visited[x][1]
                q.append(i)

            # 다음 좌표로 이동하는 시간이 현재까지 이동 시간 + 1초로 똑같다면
            # 이 경우, 첫 방문이 아니라는 의미
            # 만약 여기 조건을 단순히 첫 방문이 아닌 경우 (visited[i][0] != 1)로 잡으면
            # 최단 소요 시간인지 확인할 방법이 없음
            # => 재방문이면서, 이전 좌표까지 온 소요 시간에 +1한 값과 같아야 i까지 오는데 소요된 최단 시간이 됨
            elif visited[i][0] == visited[x][0] + 1:
                
                # 다음 좌표에 도착하는 기존 경우의 수에 현재 좌표로 도착하는 경우의 수를 더함
                visited[i][1] += visited[x][1]
                
bfs(n)

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

문제 해설

숨바꼭질의 변형 문제.

기존의 문제가 동생을 찾는 최단 시간을 찾는 문제였다면, 이 문제의 경우 기존의 문제에 최단 시간으로 동생을 찾는 방법의 수까지 구해야 하는 문제이다. 따라서, n -> k로 가는 최단 시간을 X라고 할 때 X를 가지는 경우의 수를 별도로 받아야 한다. 이 부분을 방문 체크를 하는 리스트를 2차원으로 구성하여 표현해준다.

  • visited[i][0] => i에 방문하는데 소요된 시간
  • visited[i][1] => 소요 시간을 같는 경우의 수의 개수

위와 같이 2차원 배열로 k에 도착하는 최단 시간과 그 시간을 가질 수 있는 경우의 수를 담아주는데 이전까지의 방문이 동일한 경우인지 아니면 새로운 경로로 도착한 경우인지 분기를 나누는 것이 생각보다 어려웠다.

이 부분은 기존 숨바꼭질 문제의 로직에 아래의 조건문을 추가하여 구현할 수 있었다.

 elif visited[i][0] == visited[x][0] + 1:
                
	# 다음 좌표에 도착하는 기존 경우의 수에 현재 좌표로 도착하는 경우의 수를 더함
	visited[i][1] += visited[x][1]

댓글남기기

참고