글 읽기 - 더 최적화가 가능한가요?

(追記) (追記ここまで)

더 최적화가 가능한가요?

9019번 - DSLR

youshouldknowme 6달 전 0

해당 문제를 단방향 bfs + 역추적으로 구현하였는데 pypy3에서는 통과하지만 python3에서는 시간초과가 발생합니다.

양방향 bfs + 역추적으로 구현하면 python3에서도 통과할 수 있다는 건 알지만 제 코드도 더 최적화하면 python3 상에서 통과할 수 있나요?

import sys
from collections import deque
input = sys.stdin.readline
def D(num):
 return (num*2)%10000
def S(num):
 return (num+9999)%10000
def L(num):
 return num//1000+num%1000*10
def R(num):
 return num//10+num%10*1000
def find(start,end):
 com = [D,S,L,R]
 letter = ['D','S','L','R']
 visited = [-1]*10000 
 visited[start] = start
 def bfs():
 routes = deque([start])
 while routes:
 x = routes.popleft()
 for i in range(4):
 nx = com[i](x)
 if nx == end:
 visited[nx] = (x,letter[i])
 return 
 if visited[nx] == -1:
 routes.append(nx)
 visited[nx] = (x,letter[i])
 def backtracking(visited,end):
 target = end
 st = []
 while visited[target] != target:
 target, s = visited[target]
 st.append(s)
 return ''.join(st)[::-1]
 bfs()
 return backtracking(visited,end)
for _ in range(int(input())):
 reg, target = map(int,input().split())
 print(find(reg,target))

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

더 최적화가 가능한가요?

youshouldknowme 6달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말