문제
풀이
백준의 A->B 문제와 매우 유사하다. 차이점은 A->B 문제에서는 최소 연산 횟수만 구하면 되지만 이 문제에서는 최소 연산으로 연산 가능한 경우의 수 까지 함께 구해야한다는 점이 다르다. 아무튼 이 문제 또한 bfs로 풀이하면 쉽게 답을 찾을 수 있다.
일단 방문 여부 및 위치 별 최소 시간 갱신 을 위해 visited 리스트를 미리 만들어 둔다.
그 다음 큐를 준비한 뒤 수빈이의 위치를 삽입한다.( = q.append(n) )
시작 위치까지의 최소 시간은 0초 이므로 visited의 n번째는 0을 저장한다. (애초에 visited 생성할 때 0으로 초기화하기 때문에 큰 의미는 없음)
이후 while문을 돌며 큐에 원소가 존재한다면 원소를 pop한다.
만약 pop한 원소 x가 동생의 위치 k 라면, 가장 빠른 시간으로 수빈이가 동생을 찾았다고 간주할 수 있다. 따라서 최종 시간을 저장하는 변수인 ans_sec에 visited[x] 를 저장한다.
하지만 여기서 주의할 점은 동생을 찾은 경우가 이미 존재할 수 있기 때문에 ans_sec가 초기화값인 100001인지를 반드시 확인해야 한다는 점이다. 추가로 경우의 수를 카운트해주는 ans_cnt값도 1 증가시킨다.
pop한 원소가 k가 아니라면, 아직 동생을 찾기 위한 연산 과정이 남아있다는 뜻이므로 현재 원소에서 1) 1을 뺀 경우 와 2) 1을 더한 경우 그리고 3) 2를 곱한 경우를 큐에 삽입한다.
이 때 연산된 값이 범위 내에 있는지 ( 최대 위치가 100000이므로 연산 값은 200000을 넘을 수 없다 ) 그리고 연산값을 인덱스로 갖는 visited 값이 0이 아닌지 ( = 방문했던 위치인지 파악하기 위함 ) 꼭 고려해야한다.
추가로 고려해야할 사항이 있는데, 연산값을 인덱스로 갖는 visited 값이 현재 연산 값 +1 ( visited[a]==visited[x]+1 ) 인 경우도 큐에 삽입 해야한다는 것이다. 이는 최소 연산값을 갖는 경우의 수가 여러 개 있을 수 있으므로 이를 파악하기 위함이다 ( 이 행위를 통해 ans_cnt를 갱신시킬 수 있다 )
from collections import deque
import sys
input = sys.stdin.readline
n, k = map(int, input().strip().split())
visited = [0] * 200001 # 시간 갱신
def bfs():
ans_sec = 100001 # 최종 빠른 시간 저장하는 변수
q = deque()
ans_cnt = 0 # 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수
q.append(n)
visited[n] = 0
while q:
x = q.popleft()
if visited[x] > ans_sec:
break
if x == k:
if ans_sec == 100001:
ans_sec = visited[x]
if visited[x] == ans_sec:
ans_cnt += 1
continue
arr = [x - 1, x + 1, x * 2]
for a in arr:
if 0 <= a <= 200000 and (visited[a] == 0 or visited[a] == visited[x] + 1):
visited[a] = visited[x] + 1
q.append(a)
return ans_sec, ans_cnt
ans_sec, ans_cnt = bfs()
print(ans_sec)
print(ans_cnt)