문제
접근
이 문제도 방문 배열을 현재 숫자로 이용하면 된다.
L, R을 문자열로 사용한다면 연산이 쉽다.
하지만 시간초과를 해결할 수 가 없어, 결국 int형으로 몫과 나머지를 이용하여 연산을 진행했다.
하지만 이렇게 해도 시간초과가 해결이 안되서, pypy3으로 제출했다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from collections import deque
import sys
input = sys.stdin.readline
def bfs(start, target):
q = deque()
q.append(start)
board[start] = ''
while q:
now = q.popleft()
if now == target:
return board[now]
tmp = [['D', (now*2) % 10000],
['S', 9999 if now == 0 else now-1],
['L', (now % 1000) * 10 + now // 1000],
['R', (now % 10) * 1000 + now // 10]]
for command, nxt in tmp:
if board.get(nxt, -1) == -1:
q.append(nxt)
board[nxt] = board[now] + command
t = int(input())
for i in range(t):
board = {}
start, target = map(int, input().split(' '))
print(bfs(start, target))