[SW Expert Academy] 5246번 연산 python

문제의 저작권은 SW Expert Academy에 있습니다.

 

자연수 N에 몇 번의 연산을 통해 다른 자연수 M을 만들려고 한다.

사용할 수 있는 연산이 +1, -1, *2, -10 네 가지라고 할 때 최소 몇 번의 연산을 거쳐야 하는지 알아내는 프로그램을 만드시오.

단, 연산의 중간 결과도 항상 백만 이하의 자연수여야 한다.

예를 들어 N=2, M=7인 경우, (2+1) *2 +1 = 7이므로 최소 3번의 연산이 필요한다.


[입력]

첫 줄에 테스트 케이스의 개수가 주어지고, 다음 줄부터 테스트 케이스 별로 첫 줄에 N과 M이 주어진다. 1<=N, M<=1,000,000, N!=M

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

풀이.

 

첫번째 풀이는 pop 연산이다. 이때 pop을 쓰면 리스트를 앞으로 당기므로 자리변동이 일어나기 때문에 시간 초과가 뜬다.

T = int(input())

def bfs(n, m):
    visit[n] = 1  # 방문 기록
    q = [n]  # 큐에 시작 노드 인큐
    while len(q) != 0:  # 큐가 비어있지 않으면
        n = q.pop(0)  # 다음 노드를 꺼내
        t = [n + 1, n - 1, n * 2, n - 10]  # 인접 노드번호 계산
        for i in range(4):
            if t[i] == m:  # 찾는 노드인 경우 거리 리턴
                return visit[n]
            if t[i] > 0 and t[i] <= 1000000:  # 유효한 노드 번호이므로
                if visit[t[i]] == 0:  # 아직 방문하지 않은 노드면
                    visit[t[i]] = visit[n] + 1  # 거리를 기록하고
                    q.append(t[i])  # 큐에 추가


for tc in range(1, T + 1):
    N, M = map(int, input().split())
    visit = [0 for _ in range(1000000+1)]
    print('#{} {}'.format(tc, bfs(N, M)))

 

그러면 무엇을 쓰나... Queue로 폴어보니 시간 더걸린다. import queue는 나중에 임계연산으로 쓰인다. 즉, 별의 별 기능이 다 들어가 있어서 느리다.

import queue
T = int(input())

def bfs(n, m):
    q = queue.Queue()  # 큐 생성
    visit[n] = 1  # 방문 기록
    q.put(n)  # 큐에 시작 노드 인큐
    while not q.empty():  # 큐가 비어있지 않으면
        n = q.get()  # 다음 노드를 꺼내
        t = [n + 1, n - 1, n * 2, n - 10]  # 인접 노드번호 계산
        for i in range(4):
            if t[i] == m:  # 찾는 노드인 경우 거리 리턴
                return visit[n]
            if t[i] > 0 and t[i] <= 1000000:  # 유효한 노드 번호이므로
                if visit[t[i]] == 0:  # 아직 방문하지 않은 노드면
                    visit[t[i]] = visit[n] + 1  # 거리를 기록하고
                    q.put(t[i])  # 큐에 추가


for tc in range(1, T + 1):

    N, M = map(int, input().split())
    visit = [0 for _ in range(1000000+1)]
    print('#{} {}'.format(tc, bfs(N, M)))

 

이번엔 덱으로 풀어보자. 덱은 만능이다. stack도 되고 Queue도 가능하다.

import collections
T = int(input())

def bfs(n, m):
    deq = collections.deque()  # 데크 생성
    visit[n] = 1  # 방문 기록
    deq.append(n)  # 덱에 시작 노드 인큐
    while len(deq) != 0:  # 덱이 비어있지 않으면
        n = deq.popleft()  # 다음 노드를 꺼내
        t = [n + 1, n - 1, n * 2, n - 10]  # 인접 노드번호 계산
        for i in range(4):
            if t[i] == m:  # 찾는 노드인 경우 거리 리턴
                return visit[n]
            if t[i] > 0 and t[i] <= 1000000:  # 유효한 노드 번호이므로
                if visit[t[i]] == 0:  # 아직 방문하지 않은 노드면
                    visit[t[i]] = visit[n] + 1  # 거리를 기록하고
                    deq.append(t[i])  # 덱에 추가


for tc in range(1, T + 1):
    N, M = map(int, input().split())
    visit = [0 for _ in range(1000000+1)]
    print('#{} {}'.format(tc, bfs(N, M)))