1697번 숨바꼭질

문제 설명

1697번: 숨바꼭질

 

나의 풀이

from collections import deque, defaultdict


def bfs(start_number, target_number):
    q = deque()
    q.append(start_number)
    distance_dict = defaultdict(int)
    distance_dict[start_number] = 0

    dx = [-1, 1]
    while q:
        cur_num = q.popleft()

        if cur_num == target_number:
            return distance_dict[cur_num]

        for i in range(3):
            if i < 2:
                next_num = cur_num + dx[i]
            else:
                next_num = cur_num*2

            if 0<=next_num<=100000 and not distance_dict[next_num]:
                distance_dict[next_num] = distance_dict[cur_num] + 1
                q.append(next_num)

start_number, target_number = map(int, input().split())
print(bfs(start_number, target_number))

 시작하는 숫자, 타겟하는 숫자를 인자로 받아 조건에 맞게 시작하는 숫자를 타겟하는 숫자의 최단거리로 가기 위해 -1, +1, *2를 하여 타겟 값에 q자료구조를 활용하여 bfs로 접근한다.

 최단 거리를 구하기 위해 나는 defaultdict를 활용해서 접근하지 않은 값은 0이 나오게 그리고 해당 값의 거리를 전의 값보다 +1을하여 거리를 업데이트 최종적으로 cur_num이 target_num과 같아지면 리턴해주고 그 거리를 반환해준다.