[백준] 9019번 - DSLR (파이썬)

https://www.acmicpc.net/problem/9019

# DSLR
from collections import defaultdict
from collections import deque


def get_result(x, k):
    if k == 'D':
        return (x*2) % 10000
    if k == 'S':
        return x-1 if x != 0 else 9999
    if k == 'L':
        return (x % 1000)*10 + x//1000
    if k == 'R':
        return (x % 10)*1000 + x//10


T = int(input())
for _ in range(T):
    a, b = map(int, input().split())
    dict = defaultdict(str)
    dict[a] = ''
    q = deque()
    q.append(a)
    while q:
        x = q.popleft()
        if x == b:
            break
        for k in ['D', 'S', 'L', 'R']:
            result = get_result(x, k)
            if result not in dict:
                q.append(result)
                dict[result] = dict[x] + k
    print(dict[b])

 

BFS
1. 테스트 케이스 T만큼 반복
2. a, b를 입력받는다.
3. dict : 해당 숫자의 기록, dict[a] = ''
4. q를 deque로 선언, 초깃값 = a
5. bfs : q가 빌 때까지
    - q.popleft(), b와 같다면 break
    - D, S, L, R 각 명령에 대해
        - get_result : 해당 명령에 대한 결괏값 반환
        - dict에 없으면 q에 append, dict에 기존 값 + 명령어(k) 추가
6. dict[b] 출력

 

방문 여부를 확인하는 여러 방법이 있겠지만 공간 복잡도도 고려한 딕셔너리로 풀었다.

딕셔너리의 삽입, 검색은 O(1)로 작동한다. 따라서 시간 복잡도도 만족한다.