백준 9019번: DSLR 파이썬 코드(BFS)

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

import sys
from collections import deque

t = int(sys.stdin.readline())

def bfs(a1,b1):
    queue = deque([])
    queue.append([a1, ""])
    visited = [0 for _ in range(10000)]
    while queue:
        now, string = queue.popleft()
        if now == b1:
            return string
        #D---------------------------------
        temp2 = now
        now = now * 2
        if now > 9999:
            now = now % 10000
        if visited[now] == 0:
            queue.append([now, string + "D"])
            visited[now] = 1
        else:
            pass
        # S---------------------------------
        now = temp2
        now = now - 1
        if now < 0:
            now = 9999
        if visited[now] == 0:
            queue.append([now, string + "S"])
            visited[now] = 1
        else:
            pass
        # L---------------------------------
        now = temp2
        temp1 = now // 1000
        now = now % 1000
        now = now * 10 + temp1
        if visited[now] == 0:
            queue.append([now, string + "L"])
            visited[now] = 1
        else:
            pass
        # R---------------------------------
        now = temp2
        temp1 = now % 10
        now = now // 10
        now = now + (temp1 * 1000)
        if visited[now] == 0:
            queue.append([now, string + "R"])
            visited[now] = 1
        else:
            pass


for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    print(bfs(a,b))

설명

BFS로 푼다. 코드가 더럽긴한데. 문제에 적혀있는 D,S,L,R을 그대로 구현을 해주고 visited를 만들어서 이미 도달했던 숫자는 또 다시 큐에 넣지 않도록 조건문을 달아주면 끝이다.

문제점

문제자체는 그리 어렵지 않았지만, 주의해야할 점이 많다. 맨처음 함수로 따로 DSLR을 분리해서 짰다가 시간초과가 걸려서 혹시 함수에 매개변수를 넣고 리턴값을 받는게 시간이 더 걸리나? 싶어서 그냥 전부 함수를 제거하고, 그냥 while문 안에 다 때려박았다. 그래도 시간초과가 생겨서 고민한 결과 visited를 사용해야한다는 것을 깨닫고 visited를 추가했으나. 시간초과는 해결되었지만 그냥 틀렸다고 나왔다. 아 문제를 잘 안읽어서 생긴 문제였다. S 에서 0 미만이 되어야 9999로 바꿔줘야하는데 0이 될때 9999로 바꿔버려서 틀리는 것이였다. 코드의 기본틀을 짜는 시간은 오래걸리지 않았다. 다만 그 코드에서 변형하는 시간이 좀 걸렸다.