알고리즘

백준[Python] - 9019 : DSLR

BKM 2024. 4. 17. 23:03

문제

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

 

9019번: DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에

www.acmicpc.net

 

풀이

# DSLR
import sys
from collections import deque
input = sys.stdin.readline

def D(n):
    return n*2 if n*2<10000 else (n*2)%10000

def S(n):
    return n-1 if n-1>=0 else 9999

def L(n):
    n = str(n).zfill(4)
    return int(n[1:]+n[0])

def R(n):
    n = str(n).zfill(4)
    return int(n[-1]+n[:-1])
        
def bfs(n,target):
    q = deque([(n,'')])
    while q: 
        n,answer = q.popleft()
        for func in funcs:
            res = globals()[f'{func}'](n)
            if res==target:
                return answer+func
            else:
                if not visited[res]:
                    visited[res]=True
                    q.append((res,answer+func))
                       
funcs = ['D','S','L','R']
t = int(input().strip())
for _ in range(t):
    visited = [False]*10000
    a,b = map(int, input().strip().split())
    answer = bfs(a,b)
    print(answer)

 

더 빠른 코드

함수 호출을 적게 할수록 시간, 메모리 효율적으로 바뀌는 것 같다.

# DSLR
import sys
from collections import deque
input = sys.stdin.readline

def D(n):
    return n*2 if n*2<10000 else (n*2)%10000

def S(n):
    return n-1 if n-1>=0 else 9999

def L(n):
    n = str(n).zfill(4)
    return int(n[1:]+n[0])

def R(n):
    n = str(n).zfill(4)
    return int(n[-1]+n[:-1])
        
def bfs(n,target):
    q = deque([(n,'')])
    while q: 
        n,answer = q.popleft()
        for func in funcs:
            # res = globals()[f'{func}'](n)
            if func=='D':
                res = n*2 if n*2<10000 else (n*2)%10000
            elif func=='S':
                res = n-1 if n-1>=0 else 9999
            elif func=='L':
                n = str(n).zfill(4)
                res = int(n[1:]+n[0])
            else:
                n = str(n).zfill(4)
                res = int(n[-1]+n[:-1])
                
            if res==target:
                return answer+func
            else:
                if not visited[res]:
                    visited[res]=True
                    q.append((res,answer+func))
                       
funcs = ['D','S','L','R']
t = int(input().strip())
for _ in range(t):
    visited = [False]*10000
    a,b = map(int, input().strip().split())
    answer = bfs(a,b)
    print(answer)

 

Q에 불필요한 원소를 넣는것에 대한 필터링을 잊지말자...

 

Python3로 구동되는 코드는 어떤 코드일까...