[SWEA] 5247. 연산

문제

풀이1(시간초과)

from collections import deque

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

    queue.append((N, cnt))
    while queue:
        n, c = queue.popleft()
        if n == M:
            cnt = c
            break
        elif not (0 < n <= 1000000):
            continue
        c += 1
        queue.append((n+1, c))
        queue.append((2*n, c))
        queue.append((n-1, c))
        queue.append((n-10, c))

    print(f'#{tc}', cnt)

풀이2(시간초과)

from collections import deque

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    visit = [0] * 1000001
    lst = [1, -1, 0, -10]
    queue = deque()
    cnt = 0

    queue.append(N)
    while queue:
        n = queue.popleft()
        lst[2] = n
        if n == M:
            cnt = visit[n]
            break
        for i in range(4):
            tmp = n + lst[i]
            if not (0 < tmp < 1000001):
                continue
            elif visit[tmp] != 0 and visit[tmp] < visit[n] + 1:
                continue
            visit[tmp] = visit[n] + 1
            queue.append(tmp)

    print(f'#{tc}', cnt)

풀이3

from collections import deque

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    visit = [0] * 1000001
    queue = deque()
    cnt = 0

    queue.append((N, 0))
    while queue:
        n, c = queue.popleft()
        if n == M:
            cnt = c
            break
        c += 1
        if 0 < n+1 < 1000001 and visit[n+1] == 0:
            visit[n+1] = 1
            queue.append((n+1, c))
        if 0 < n-1 < 1000001 and visit[n-1] == 0:
            visit[n-1] = 1
            queue.append((n-1, c))
        if 0 < 2*n < 1000001 and visit[2*n] == 0:
            visit[2*n] = 1
            queue.append((2*n, c))
        if 0 < n-10 < 1000001 and visit[n-10] == 0:
            visit[n-10] = 1
            queue.append((n-10, c))

    print(f'#{tc}', cnt)

풀이4(풀이2 수정)

• visit 값으로 cnt 값 대신

from collections import deque

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    visit = [0] * 1000001
    queue = deque()
    cnt = 0

    queue.append(N)
    while queue:
        n = queue.popleft()
        if n == M:
            cnt = visit[n]
            break
        tmp = visit[n] + 1
        if 0 < n+1 < 1000001 and (visit[n+1] == 0 or visit[n+1] > tmp):
            visit[n+1] = tmp
            queue.append(n+1)
        if 0 < n-1 < 1000001 and (visit[n-1] == 0 or visit[n-1] > tmp):
            visit[n-1] = tmp
            queue.append(n-1)
        if 0 < 2*n < 1000001 and (visit[2*n] == 0 or visit[2*n] > tmp):
            visit[2*n] = tmp
            queue.append(2*n)
        if 0 < n-10 < 1000001 and (visit[n-10] == 0 or visit[n-10] > tmp):
            visit[n-10] = tmp
            queue.append(n-10)

    print(f'#{tc}', cnt)

• 걍 deque + visit 안 쓰면 시간 초과 뜸