[알고리즘][Python] 백준 9019 DSLR 문제 풀이

문제 출처 : www.acmicpc.net/problem/9019

9019번: DSLR

---

문제 해석 : 각각 주어지는 DSLR의 조건을 확인하면서 연산을 수행해 원하는 숫자가 나올때 까지의 연산을 출력하는 문제이다.

 

문제 풀이 : 이 문제 또한 BFS문제이다. 각각의 결과와 명령들을 저장한 배열을 큐에 넣고 원하는 결과가 나올 때 까지 반복하면 문제를 풀 수 있다. 다만 visited 처리를 해줘야 시간 초과, 메모리 초과를 벗어 날 수 있다.

---

풀이 코드

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

T = int(input())

for test_case in range(T):
    A, B = map(int, input().split())

    visited = [0 for _ in range(10000)]

    Q = deque()
    Q.append([A,""])
    visited[A] = 1
    answer = ""

    while Q:

        target, instruction = Q.popleft()

        if target == B:
            answer = instruction
            break

        if 2*target <= 9999 and visited[2*target] == 0:
            visited[2*target] = 1
            Q.append([2*target, instruction + "D"])

        if 2 * target > 9999 and visited[(2 * target) % 10000] ==0:
            visited[(2*target) % 10000] = 1
            Q.append([(2*target)%10000, instruction + "D"])

        if target - 1 >= 0 and visited[target -1] == 0:
            visited[target - 1] = 1
            Q.append([target-1, instruction + "S"])

        if target -1 < 0 and visited[9999] == 0:
            visited[9999] = 1
            Q.append([9999, instruction + "S"])

        L_move = int((target % 1000) * 10 + target / 1000)
        if visited[L_move] == 0:
            visited[L_move] = 1
            Q.append([L_move, instruction+"L"])

        R_move = int((target % 10) * 1000 + target / 10)
        if visited[R_move] == 0:
            visited[R_move] = 1
            Q.append([R_move, instruction + "R"])

    print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.