[백준] 9019 DSLR (python 파이썬)

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

9019번: DSLR

---

아이디어

1. bfs

• 최소한의 명령 어을 출력 하라 했으므로 bfs가 아니면 못 풀 거 같다고 생각했다.
• 시간제한도 6초로 넉넉하게 있어서 충분하다고 생각했다.

2. 시간 초과

• 요즘 계속 시간 초과가 뜬다. 6초라서 넉넉할 줄 알았는데.
• 시간 초과가 뜬이유는 다음과 같다.
• D, S, L, R 각각의 명령어를 간소하게 구현해야 했는데, if문이나 리스트를 사용해 시간제한이 걸린 거 같다.
• 수학적으로 먼저 접근했으면 좋았을 거 같다.

3. DSLR 명령어

• D와 S는 금방 방법을 떠오를 수 있다. S는 음수 나눗셈에 대해 알고 있다면 좋다.
• L과 R은 이 문제에서는 자릿수가 정해져 있으므로 사칙연산으로도 구현 가능하다.
• 직접 종이에 적어가며 수식을 만드는 게 도움이 됐다.

---

코드 설명

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

    if num == B:
        print(command)
        break

    d = num * 2 % 10000
    if not visited[d]:
        visited[d] = True
        deq.append([d, command + 'D'])

    s = (num - 1) % 10000
    if not visited[s]:
        visited[s] = True
        deq.append([s, command + 'S'])

    l = num // 1000 + (num % 1000)*10
    if not visited[l]:
        visited[l] = True
        deq.append([l, command + 'L'])

    r = num // 10 + (num % 10) * 1000
    if not visited[r]:
        visited[r] = True
        deq.append([r, command + 'R'])

bfs에 대한 내용은 간단하다.

숫자를 변형하면서 이 숫자를 방문한 적이 있는지 체크해가며 명령어를 추가하면 된다.

 

중요한 건 명령어 부분이다.

D나 S 같은 부분은 문제 조건에 맞게 적어주면 된다.

 

L이나 R 같은 경우는 신경을 써줘야 한다. 

예를 들어 123이 있다고 하면. 왼쪽으로 회전하면 231이 아니고 1230이 되고,

오른쪽으로 회전하면 3012가 된다. 

짧은 수식이므로 공책이나 메모장에 간단하게 써보는 것이 좋다. 바로 생각나면 더 좋고

 

본인은 deque를 사용해 rotate함수를 썼는데 이것이 시간 초과의 원인인 것 같다.

---

전체 코드

import sys
from collections import deque
T = int(input())

for _ in range(T):
    A, B = map(int,sys.stdin.readline().rstrip().split())

    visited = [False for i in range(10001)]
    deq = deque()
    deq.append([A,''])
    visited[A] = True

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

        if num == B:
            print(command)
            break

        d = num * 2 % 10000
        if not visited[d]:
            visited[d] = True
            deq.append([d, command + 'D'])

        s = (num - 1) % 10000
        if not visited[s]:
            visited[s] = True
            deq.append([s, command + 'S'])

        l = num // 1000 + (num % 1000)*10
        if not visited[l]:
            visited[l] = True
            deq.append([l, command + 'L'])

        r = num // 10 + (num % 10) * 1000
        if not visited[r]:
            visited[r] = True
            deq.append([r, command + 'R'])

pypy3로 제출 여담으로 python3로 맞춘 사람은 10명도 안된다.