백준 9019 DSLR

gmlwlswldbs·2022년 1월 14일
0

코딩테스트

목록 보기
108/130
from collections import deque

def op_d(x):
    return 'D', (x * 2) % 10000
def op_s(x):
    return 'S', (x - 1) % 10000
def op_l(x):
    a = x // 1000
    b = (x - a * 1000) // 100
    c = (x - a * 1000 - b * 100) // 10
    d = x - a * 1000 - b * 100 - c * 10
    tmp = b * 1000 + c * 100 + d * 10 + a
    return 'L', tmp
def op_r(x):
    a = x // 1000
    b = (x - a * 1000) // 100
    c = (x - a * 1000 - b * 100) // 10
    d = x - a * 1000 - b * 100 - c * 10
    tmp = d * 1000 + a * 100 + b * 10 + c
    return 'R', tmp

t = int(input())

for _ in range(t):
    a, b = map(int, input().split())
    q = deque()
    d = [-1] * 10000
    q.append((a, ''))
    d[a] = 0
    while q:
        x, ops = q.popleft()
        if x == b:
            print(ops)
            break
        for op, y in [op_d(x), op_s(x), op_l(x), op_r(x)]:
            tmp_ops = ops
            if d[y] == -1:
                d[y] = d[x] + 1
                tmp_ops += op
                q.append((y, tmp_ops))

bfs로 돌려줌. 처음에는 DSLR연산을 문자열 처리 했는데

def op_d(x):
    return 'D', (x * 2) % 10000
def op_s(x):
    return 'S', (x - 1) % 10000
def op_l(x):
    x = str(x)
    tmp = x[1:] + x[0]
    return 'L', int(tmp)
def op_r(x):
    x = str(x)
    tmp = x[-1] + x[:len(x)-1]
    return 'R', int(tmp)

시간 초과 남.. 문자열 처리는 시간이 많이 걸리나보다....

0개의 댓글