[SWEA/Python] 5247. 연산

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. bfs를 활용해서 각 계산값에 접근하는 방식으로 풀었다.
2. 최대 재귀 깊이를 넘어가길래 가지치기를 해줬는데, 첫 번째 코드처럼 append하고 not in으로 탐색하는 방식은 시간초과가 났다.
3. 그래서 두 번째 코드처럼 처음부터 모든 숫자만큼 리스트를 만들어주고 숫자가 중복되지 않도록 이미 나온 숫자는 1로 바꿔줬다.

 

📌 코드

from collections import deque

def find_M(N):
    queue = deque()
    queue.append((N, 0))

    numbers = [N]

    while queue:
        number, cnt = queue.popleft()

        if number == M:
            return cnt
        
        if number+1 <= 1000000 and number+1 not in numbers:
            numbers.append(number+1)
            queue.append((number+1, cnt+1))
        if number-1 > 0 and number-1 not in numbers:
            numbers.append(number-1)
            queue.append((number-1, cnt+1))
        if number*2 <= 1000000 and number*2 not in numbers:
            numbers.append(number*2)
            queue.append((number*2, cnt+1))
        if number-10 > 0 and number-10 not in numbers:
            numbers.append(number-10)
            queue.append((number-10, cnt+1))


T = int(input())

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

    print('#{} {}'.format(t, find_M(N)))

→ 시간 초과

 

from collections import deque
import sys
sys.stdin = open('input.txt')

def find_M(N):
    global numbers

    queue = deque()
    queue.append((N, 0))

    numbers[N] = 1

    while queue:
        number, cnt = queue.popleft()

        if number == M:
            return cnt
        
        if number+1 <= 1000000 and not numbers[number+1]:
            numbers[number+1] = 1
            queue.append((number+1, cnt+1))

        if number-1 > 0 and not numbers[number-1]:
            numbers[number-1] = 1
            queue.append((number-1, cnt+1))

        if number*2 <= 1000000 and not numbers[number*2]:
            numbers[number*2] = 1
            queue.append((number*2, cnt+1))

        if number-10 > 0 and not numbers[number-10]:
            numbers[number-10] = 1
            queue.append((number-10, cnt+1))


T = int(input())

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

    numbers = [0 for _ in range(1000001)]

    print('#{} {}'.format(t, find_M(N)))