[백준] 9019번 DSLR _ Python

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

9019번: DSLR

 

 

---

 

1. Preview

시간 복잡도: O(4*commands)

 

공간 복잡도: O(commands)

 

 

---

 

2. 초기 접근 방법

현재 풀이와 똑같이,

queue()를 사용해 수행한 연산을 순서에 맞게 처리하여, 최소 연산 커맨드를 찾으려고 했다.

 

 

하지만 2가지 간과한 점이 있어 '시간초과'와 '틀렸습니다'를 받았다.

 

1) visited[num] = T/F (시간초과)

방문한 숫자에 대해서, 이전에 DSLR 연산을 수행한 적이 있으면 재연산을 하지 않아도 된다

 

2) '0' shift (틀렸습니다)

'0'을 포함해서 shift 한 것이 아니라, 숫자 자릿수에 맞춰서 shift를 했다.

num = 219
l = len(str(num))
print(num)
print()

# L
print((num % 1000 * 10) + (num // 1000))
print((num % pow(10, l - 1) * 10) + (num // pow(10, l - 1)))

print()

# R
print((num % 10 * 1000) + (num // 10))
print((num % 10 * (pow(10, l - 1))) + (num // 10))

 

219

2190
192

9021
921

 

 

---

 

3. 생각

 

정확하고, 빠르게 풀자.

 

 

---

 

4. 코드

from collections import deque

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

    visited = [False for _ in range(10000)]
    visited[A] = True

    q = deque()
    q.append([A, ""])

    while q:
        num, command = q.popleft()

        if num == B:
            print(command)
            break

        numD = (num * 2) % 10000
        if not visited[numD]:
            visited[numD] = True
            q.append([numD, command + "D"])
        
        numS = (num - 1) % 10000
        if not visited[numS]:
            visited[numS] = True
            q.append([numS, command + "S"])

        l = len(str(num))
        numL = (num % 1000 * 10) + (num // 1000)
        if not visited[numL]:
            visited[numL] = True
            q.append([numL, command + "L"])

        numR = (num % 10 * 1000) + (num // 10)
        if not visited[numR]:
            visited[numR] = True
            q.append([numR, command + "R"])