[SWEA] 5247_연산

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

1. set으로 visited를 만든다.

2. bfs를 이용해서 +1, -1, *2, -10 네 가지의 연산한 결과값이 현재까지 나온 숫자가 아니고 백만보다 작다면 결과값과 지금까지의 연산 횟수를 deq에 넣는다.

3. 그리고 결과값을 visited에 담는다. (다른 연산에서 같은 결과값이 나왔다면 굳이 계속해서 연산을 진행할 필요가 없기 때문에 -> 실행시간 절약)

4. 만약 n이 M이 된다면 c(지금까지의 연산횟수)를 출력한다.

 

from collections import deque

def bfs(n, c):
    deq = deque([(n, c)])
    visited = set()
    visited.add(n)

    while deq:
        n, c = deq.popleft()

        if n == M:
            return c

        if n*2 not in visited and n*2 <= 1000000:
            deq.append((n*2, c+1))
            visited.add(n*2)
        if n+1 not in visited and n+1 <= 1000000:
            deq.append((n+1, c+1))
            visited.add(n+1)
        if n-1 not in visited and n-1 <= 1000000:
            deq.append((n-1, c+1))
            visited.add(n-1)
        if n-10 not in visited and n-10 <= 1000000:
            deq.append((n-10, c+1))
            visited.add(n-10)

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())

    print('#{} {}'.format(tc, bfs(N, 0)))