[백준 9019] DSLR - python (solved.ac - 골드 5)

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

9019번: DSLR

풀이

문제를 보았을때 알수있는 힌트

먼저 pypy3로 푸는 것이 좋다. 실제 확인해보니 python으로 푼사람이 8명도 안된다..;;

문제를 보고 반복 시키기에는 너무 많은 양을 반복해야할듯해서 BFS를 통해 풀면 될듯하다는생각을 가졌다.

dfs는 방문을 했는지만 체크하면 확실히 시간을 줄일 수 있다.

이를 유의하여 문제를 풀면 된다.

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

t= int(input())

for _ in range(t):
    a,b = map(int,input().split())
    visited=[False for _ in range(10001)]
    result=deque([[a,""]])
    while result:
        v= result.popleft()
        temp=(v[0]*2)%10000
        if temp==b:
            print(v[1]+"D")
            break
        elif visited[temp]==False:
            visited[temp]=True
            result.append([temp,v[1]+"D"])
        temp = v[0]-1
        if temp==-1:
            temp=9999
        if temp==b:
            print(v[1]+"S")
            break
        elif visited[temp]==False:
            visited[temp]=True
            result.append([temp,v[1]+"S"])
        temp=int(v[0]%1000*10+v[0]/1000)
        if temp==b:
            print(v[1]+"L")
            break
        elif visited[temp]==False:
            visited[temp]=True
            result.append([temp,v[1]+"L"])
        temp=int(v[0]%10*1000+v[0]//10)
        if temp==b:
            print(v[1]+"R")
            break
        elif visited[temp]==False:
            visited[temp]=True
            result.append([temp,v[1]+"R"])

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon9019.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리