[백준] 9019번: DSLR (파이썬)

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

 

문제를 보고, 이 문제도 BFS로 풀 수 있겠다. 라고 생각하고 BFS로 풀어나갔다.

시간 제한이 6초여서 모든 경우의 수를 queue에 넣어가도 괜찮을 거라고 생각했다.

 

from collections import deque
t = int(input())

def bfs(a,b):
    queue = deque([(a,"")])
    cnt = 0
    visited = [False] * 10000
    visited[int(a)] = True
    
    while True:
        length = len(queue)
        for _ in range(length):
            da, cmd = queue.popleft()
            #A와 B가 같아질 경우
            if da == b:
                print(cmd)
                return
            else:
                #1.D
                temp = (2*int(da)) % 10000
                if not visited[temp]:
                    visited[temp] = True
                    queue.append((str(temp),cmd+"D"))
                #2.S
                if da == "0":
                    temp = 9999
                else:
                    temp = int(da) - 1
                if not visited[temp]:
                    visited[temp] = True
                    queue.append((str(temp),cmd+"S"))
                    
                # 3. L 명령어 (왼쪽 회전)
                current_str = str(da).zfill(4)  # 4자리 문자열로 변환
                next_l = int(current_str[1:] + current_str[0])
                if not visited[next_l]:
                    visited[next_l] = True
                    queue.append((str(next_l), cmd + "L"))

                # 4. R 명령어 (오른쪽 회전)
                next_r = int(current_str[-1] + current_str[:-1])
                if not visited[next_r]:
                    visited[next_r] = True
                    queue.append((str(next_r), cmd + "R"))
        
for _ in range(t):
    a,b = map(str, input().split())
    bfs(a,b)

D,S,L,R의 기능을 각각 수행해서 queue에 담는다.

이것을 A와 B가 같을 때 까지 계속해서 반복한다.

 

처음엔 visited 없이 중복되는 수도 queue에 넣었다가 메모리 초과가 되어, 이미 방문한 수는 다시 방문하지 못하게 하였다.

오답 종류도 참 많다..

이제 BFS 문제는 자신감이 조금 생긴 것 같다!