[SWEA] 5247: 연산

# 문제 설명

정수 n, m값이 주어졌을 때, 다음 4가지 연산만을 사용하여 n값에서 m값에 도달해야한다.

- 4가지 연산 : +1, -1, *2, -10

 

n에서 m에 도달하는 최소한의 연산 횟수를 구한다.

단, 중간 연산 결과는 백만(1000000) 이하의 자연수다.

 

# 입출력 예시

첫 줄은 테스트 케이스 개수이고, 다음 줄부터 n, m이 주어진다.

입력	출력
3 2 7 3 15 36 1007	#1 3 #2 4 #3 8

 

# 코드 풀이

from collections import defaultdict
from collections import deque

def get_min_op(n, m):
    visited = defaultdict(bool) # 방문했는지
    d = defaultdict(int) # 최단거리
    
    d[n] = 0
    q = deque([n]) # 속도향상을 위해
    visited[n] = True
    while len(q) > 0:
    	v = q.popleft()
        for w in [v+1, v-1, v*2, v-10]:
            if not visited[w] and w <= 1000000:
            	q.append(w)
                visited[w] = True
                d[w] = d[v]+1 # 거리 증가
                if w==m:
                    return d[w]

for i in range(int(input())):
    n, m = list(map(int, input().split(' ')))
    print('#{} {}'.format(i+1, get_min_op(n, m)))
return

 

# 핵심 포인트

- 하나의 값을 가지고 4가지 연산을 적용해 나아가므로, 그래프 알고리즘 중 너비우선탐색을 사용한다.

- 가장 먼저 방문한 것이 최단거리이므로, m값인 걸 확인하자마자 반환한다.

- 속도 향상을 위해 list대신 deque를 사용한다.