백준 9019 DSLR Python 3

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

9019번: DSLR

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ9019.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque
def BFS(A, B, visit, q):
    q.append([A, ""])
    visit[A] = 1
    while q:
        a, cmd = q.popleft()
        if a == B:
            return cmd
        #D
        new_a = (a*2) % 10000
        if not visit[new_a]:
            q.append([new_a, cmd+"D"])
            visit[new_a] = 1

        #S
        if a == 0: new_a = 9999
        else: new_a = a-1
        if not visit[new_a]:
            q.append([new_a, cmd+"S"])
            visit[new_a] = 1

        #L
        str_a = str(a).zfill(4)
        new_a = int((str_a[1]+str_a[2]+str_a[3]+str_a[0]))
        if not visit[new_a]:
            q.append([new_a, cmd+"L"])
            visit[new_a] = 1

        #R
        new_a = int((str_a[3]+str_a[0]+str_a[1]+str_a[2]))
        if not visit[new_a]:
            q.append([new_a, cmd+"R"])
            visit[new_a] = 1

input = sys.stdin.readline
T = int(input())
visit = [0]*10001
q = deque(list())

for _ in range(T):
    visit = [0] * 10001
    q.clear()
    A, B = list(map(int, input().split()))
    print(BFS(A, B, visit, q))

---

풀이 과정

풀이 시간 40분

최소한의 명령어를 사용해서 A라는 숫자를 B로 만들어야 한다.

이때 사용한 명령어를 순서대로 출력하는 문제다.

명령어는 총 4가지가 있다.

1. D: 2*n % 10000
2. S: n != 0 -> n-1, n = 0 -> 9999
3. L: n의 각 자리수를 d1 d2 d3 d4라 하였을 때, 왼쪽으로 한 칸 회전시킨 결과 -> d2 d3 d4 d1
4. R: n의 각 자리수를 d1 d2 d3 d4라 하였을 때, 오른쪽으로 한 칸 회전시킨 결과 -> d4 d1 d2 d3

문제에서 테스트 케이스 개수 T의 범위가 주어지지 않았다.

T가 크다면 복잡도 역시 커질 것이다.

Python 3으로 제출한 결과 시간초과가 발생해서 Pypy 3으로 제출하여 문제를 풀 수 있었다.

import sys
from collections import deque
def BFS(A, B, visit, q):
	#숫자 A, 명령어 초기값을 q에 담는다
    q.append([A, ""])
    #중복 탐색을 방지하기 위해 숫자 A를 visit 처리한다
    visit[A] = 1
    while q:
        a, cmd = q.popleft()
        
        #a가 B와 같은 경우, 명령어를 반환하고 함수 종료
        if a == B:
            return cmd
            
        #D 명령어 수행
        new_a = (a*2) % 10000
        if not visit[new_a]:
            q.append([new_a, cmd+"D"])
            visit[new_a] = 1

        #S 명령어 수행
        #a가 0인 경우, 9999가 된다
        if a == 0: new_a = 9999
        #a가 0이 아닌 경우, 1을 빼준다
        else: new_a = a-1
        if not visit[new_a]:
            q.append([new_a, cmd+"S"])
            visit[new_a] = 1

        #L 명령어 수행
        #a가 4자리 수 미만이라면 0을 채워 4자리 수로 바꿔준다
        str_a = str(a).zfill(4)
        #왼쪽으로 한 칸 회전
        new_a = int((str_a[1]+str_a[2]+str_a[3]+str_a[0]))
        if not visit[new_a]:
            q.append([new_a, cmd+"L"])
            visit[new_a] = 1

        #R 명령어 수행
        #오른쪽으로 한 칸 회전
        new_a = int((str_a[3]+str_a[0]+str_a[1]+str_a[2]))
        if not visit[new_a]:
            q.append([new_a, cmd+"R"])
            visit[new_a] = 1

input = sys.stdin.readline
T = int(input())
visit = [0]*10001
q = deque(list())

for _ in range(T):
    visit = [0] * 10001
    q.clear()
    A, B = list(map(int, input().split()))
    print(BFS(A, B, visit, q))

#시간복잡도 = O(T*(V+E)), 공간복잡도 = O(n)