백준 9019번 : DSLR in Python

9019번: DSLR

 

www.acmicpc.net

이 문제는 네 개의 명령어를 가지는 계산기로 어떤 수를 다른 수로 바꾸는 방법을 찾는 문제이다.

특히 최소의 명령어를 이용해 목표로 하는 수에 도달해야 하기 때문에 너비 우선 탐색을 이용해야 한다. 우선 처음에 주어진 수 A로부터 x라는 수까지 도달하기 위해 필요한 최소한의 명령어 나열을 저장하는 배열 nums을 만든다. 예를 들어 만약 A로부터 x까지 도달하기 위해 'L' 연산을 두 번 반복한 경우 nums[x] = 'LL'이 된다. 그리고 nums의 모든 성분은 아직 도달하지 않았다는 의미로 -1이라는 값으로 초기화하고, nums[A]는 빈 문자열로 초기화한다.

이후 너비 우선 탐색을 진행한다. 일단 queue에 A를 넣고 queue의 길이가 0보다 큰 동안 while loop을 돌면서 queue에서 수 u를 하나 뽑아 만약 u가 목표 수 B와 같은 경우 nums[B]를 출력하고, 너비 우선 탐색을 종료한다. 그리고 u에 명령어를 수행한 결과 나온 수를 y라고 할 때 만약 nums[y]가 -1인 경우 queue에 x를 넣고 nums[x]는 nums[u]에 명령어 문자를 더한 문자열을 넣는다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    # 0부터 9999까지 각 숫자에 도달하기 위해 최소 명령어 나열을 저장하기 위한 배열
    nums = [-1 for _ in range(10000)]
    queue = deque()
    queue.append(A)
    nums[A] = ''
    while len(queue) > 0:
        u = queue.popleft()
        if u == B:
            print(nums[B])
            break
        # 'D' 연산
        if nums[(2*u)%10000] == -1:
            queue.append((2*u)%10000)
            nums[(2*u)%10000] = nums[u] + 'D'
        # 'S' 연산으로 0일 때도 고려해 u-1 대신 (u+9999)%10000으로 구현한다.
        if nums[(u+9999)%10000] == -1:
            queue.append((u+9999)%10000)
            nums[(u+9999)%10000] = nums[u] + 'S'
        # 'L' 연산
        if nums[(u%1000)*10+u//1000] == -1:
            queue.append((u%1000)*10+u//1000)
            nums[(u%1000)*10+u//1000] = nums[u] + 'L'
        # 'R' 연산
        if nums[u//10+(u%10)*1000] == -1:
            queue.append(u//10+(u%10)*1000)
            nums[u//10+(u%10)*1000] = nums[u] + 'R'