[백준] 9019 - DSLR (BFS, PyPy)

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

9019번: DSLR

from collections import deque
import sys
 
input = sys.stdin.readline
 
t = int(input())
 
for _ in range(t):
    visited = [False] * 10000
    a, b = map(int, input().split())
 
    q = deque()
    if a == b:
        print()
    else:
        q.append((a, ''))
 
    while q:
        val, history = q.popleft()
 
        # D
        d = (val * 2) % 10000
        if d == b:
            print(history + 'D')
            break
        elif not visited[d]:
            q.append((d, history + 'D'))
            visited[d] = True
 
        # S
        s = 0
        if val == 0:
            s = 9999
        else:
            s = val - 1
        if s == b:
            print(history + 'S')
            break
        elif not visited[s]:
            q.append((s, history + 'S'))
            visited[s] = True
 
        # L
        l = (val % 1000) * 10 + val // 1000
        if l == b:
            print(history + 'L')
            break
        elif not visited[l]:
            q.append((l, history + 'L'))
            visited[l] = True
 
        # R
        r = (val % 10) * 1000 + val // 10
        if r == b:
            print(history + 'R')
            break
        elif not visited[r]:
            q.append((r, history + 'R'))
            visited[r] = True

하..

그냥 bfs로 풀면 된다.

잘못된게 없는데 왜 계속 틀렸다고 하는지 의아했는데

무조건 4자리 수를 유지해야 했다.. 내가 이해를 잘못한 것도 있지만 이건 좀;;

예를 들어, 1을 L연산 하면 1이 되는게 아니라, 10이 되고, R연산을 하면 1000이 되어야 한다.

이것만 조심하면 된다.

그리고, 파이썬은 PyPy3로 돌려야 시간초과 안난다.