[SWEA] 5247. 연산

최소 몇 번의 연산을 거쳐야 하는지 알아내는 프로그램이기 때문에 BFS로 푸는 문제이다.

deque를 사용해야 시간초과가 생기지 않는 다는 점을 알게 된 문제였다.

그리고 2+1 =3 , 3-1 =2가 반복하여 생길 수 가 있는데 이러한 문제를 예방하기 위해서 연산 결과 숫자를 인덱스로하는 리스트로 visited를 사용했고 방문했다고  처리해줬다.

from collections import deque
# 연산: +1, -1, *2, -10 네 가지
# 큐에 숫자연산결과와 횟수 함께 넣기
def oper():
    global result
    while Q: #큐가 비어있지 않으면
        front, check = Q.popleft()
        if front == M:
            result = check
            return #함수 종료
        for i in range(4):
            if i == 0:
                if 1 <= front + 1 <= 1000000 and visited[front+1] == False:
                    Q.append((front+1, check+1))
                    visited[front+1] = True
            elif i == 1:
                if 1 <= front - 1 <= 1000000 and visited[front-1] == False:
                    Q.append((front-1, check+1))
                    visited[front - 1] = True
            elif i == 2:
                if 1 <= front * 2 <= 1000000 and visited[front*2] == False:
                    Q.append((front*2, check+1))
                    visited[front * 2] = True
            elif i == 3:
                if 1 <= front - 10 <= 1000000 and visited[front-10] == False:
                    Q.append((front-10, check+1))
                    visited[front - 10] = True


T = int(input())
for tc in range(1, T + 1):
    N, M = map(int, input().split())
    result = 0
    visited = [False] * 1000001 #방문확인
    Q = deque()
    Q.append((N,0))
    oper()

    print("#{} {}".format(tc,result))