골드 IV

문제 분석 요약

BFS

💡알고리즘 설계

1~10000 미만의 십진수 내에서 탐색 가능하므로 다 탐색해도 괜찮은

BFS를 사용한다.

그리고 각 명령어를 수행한 뒤 적용 값으로 명령어를 계속 수행해야 하기 때문에 BFS로 탐구한다.

D,S,L,R의 함수를 만들고 BFS로 적용값 중 a==b가 되는 경우를 찾는다.

queue에 초기값인 a를 넣고, 명령어는 ‘’로 초기화한다.

이후, queue에서 값을 빼가며 n,case를 확인한다.

n≠b이면, 명령어 모음집을 다 실행해보면서, 그 숫자를 아직 만들지 못했을 경우 queue에 더하여 함수를 적용시킬 qeueu에 넣는다.

이때, 함수 이름을 그대로 str에 적용하기 위하여 function.__name__으로 함수 이름을 가져왔다.

💡코드

import sys
from collections import deque
input= sys.stdin.readline
t = int(input())

n=0

def D():
    if 2*n>9999:
        return (2*n)%10000
    else:
        return 2*n
    
def S():
    if n==0:
        return 9999
    else:
        return n-1
    
def L():
    return n // 1000 + (n % 1000)*10

def R():                        
    return n // 10 + (n % 10) * 1000
func = [D,S,L,R]

for _ in range(t):
    a,b = map(int,input().strip().split(' '))
    visited=[0 for _ in range(10000)]
    queue = deque()
    queue.append((a,''))
    while queue:
        n,case= queue.popleft()
        if n == b:
            print(case)
            break   
        for i in range(4):
            case_n  = func[i]()
            if visited[case_n]==0:
                queue.append((case_n,case+str(func[i].__name__)))
                visited[case_n]=1

💡틀린 이유

BFS인것은 알았으나, function을 적용한 값을 전부 queue에 넣어도 되는지 고민됐다.

💡 기억할 것

함수 이름만 넣은 뒤, 실행할 때 ()를 붙여줘서 실행시킬 수 있다.
함수 이름은 funciton.name 으로 언더바 name을 활용해 가져올 수 있다.