백준 9019 DSLR(시간복잡도, BFS)

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

9019번: DSLR

문제를 이해하기에는 어렵지 않았다. D,S,L,R에 따른 연산을 하고 연산결과가 B랑 같으면 어떤 연산을 했는지 출력한다

 

최소한의 연산을 해야하기 때문에 그리디, BFS적으로 접근을 했고 한 경우가 계속 4가지로 나가는 완전 트리의 형태를 생각해서 그래프 문제라고 생각하고 BFS적으로 접근했다.

 

여기까지의 생각은 어렵지 않았는데 python으로 풀다보니 시간초과에서 많이 애를 먹었다.

 

1. 그래프 탐색하는 중 DP적으로 한번 연산된 결과는 다시 연산 안하기 위해서 visited list를 만들어 관리한다

visited = [False] * 10000
visited[A] = True

while queue:
    num, command = queue.popleft()
    if num == B:
        print(command)
        return
    temp = func_D(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'D'))

    temp = func_S(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'S'))

    temp = func_L(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'L'))

    temp = func_R(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'R'))

2. L,R의 연산을 형변환 str(), int()를 사용하게 되면 O(logN)만큼의 시간이 든다는 것을 알았다.

숫자 연산으로 바꾸면 O(1)이 되기 때문에 숫자 연산으로 바꿨다

 

<Before>

def func_L(data):
    data = str(data)
    data = data[1:] + data[0]
    return data

def func_R(data):
    data = str(data)[-1::-1]
    return data

<After>

def func_L(data):
    front = data % 1000
    back = data // 1000
    res = front *10 + back
    return res

def func_R(data):
    front = data % 10
    back = data // 10
    res = front * 1000 + back
    return res

def func_L(data):
    return data % 1000 * 10 + data // 1000

def func_R(data):
    return data % 10 * 1000 + data // 10

code

def func_D(data):
    data = 2 * data
    if data > 9999:
        data %= 10000
    return data

def func_S(data):
    if not data:
        return 9999
    else:
        return data-1

def func_L(data):
    data = str(data)
    data = data[1:] + data[0]
    return data

def func_R(data):
    data = str(data)[-1::-1]
    return data

from collections import deque
def search(A):
    queue = deque()
    queue.append((A,''))
    visited = [False] * 10000
    visited[A] = True

    while queue:
        num, command = queue.popleft()
        if num == B:
            print(command)
            return
        temp = func_D(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'D'))

        temp = func_S(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'S'))

        temp = func_L(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'L'))

        temp = func_R(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'R'))

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    A, B = list(map(int,input().split()))
    search(A)