12851번 숨바꼭질2

문제 링크: https://www.acmicpc.net/problem/12851

약 세시간 가량 매달린 거 같은데 푼 게 너무 기뻐서 기록해본다~!😂
tmi) 처음 접근법은 아예 답이 다르게 나오고, 다른 풀이 참고해서 중간에 무한루프도 몇번 돌아보고, 결국엔 일일이 경우 따져가며 가지치기하면서 어떻게 할지 고민해보다가 아예 기존 껄 엎고 새로 풀었다!

접근방식

BFS 문제다.

현재의 수에서 +1, -1, *2한 값 방문하지 않았으면 append 하기 👉 여기까지는 누구나 쉽게 생각할 거 같은데,

개인적으로 이 문제에서 중요한 건 경우의 수 가지치기인 거 같다.
다음 방문할 값이 0 이상, k+1 이하인 경우에만 큐에 append 했다.

따로 counter 딕셔너리 변수를 둬서 counter[레벨] = 해당 레벨에서 k와 같은 수가 나온 횟수로 기록을 하고, 가장 작은 레벨에 해당하는 value을 같이 출력하며 마무리했다.

코드

from collections import deque, defaultdict

def get_shortest_time_and_cnt(start, target):
    #edge case
    if start == target:
        return 0, 1
    if start > target:
        return start - target, 1
    
    queue = deque([(start, 0)])
    visited = [False] * 100001
    counter = defaultdict(int)
    while queue:
        pos, level = queue.popleft()
        visited[pos] = True
        if pos == target:
            counter[level] += 1
        else:
            for npos in [pos - 1, pos + 1, pos * 2]:
                if 0 <= npos <= target + 1 and not visited[npos]:
                    queue.append((npos, level + 1))
                    
    min_key = min(counter.keys())
    return min_key, counter[min_key]

n, k = map(int, input().split())
time, cnt = get_shortest_time_and_cnt(n, k)
print(time)
print(cnt)