[백준] 9019 DSLR

---

주어진 수를 목표 숫자로 만들기 위한 최소한의 연산을 구하는 문제이다.

 

간단하게 BFS를 동해서 해결이 가능하다. 하지만 알고리즘 구현 중 여러 실수를 하였다.

 

1. 단순히 최소한이라는 말에 혹하여 우선순위 큐를 사용하였다.

BFS를 통해 트리를 그려보면 일반적인 큐와 우선순위 큐가 동일하게 작동한다.

 

2. 중복되는 수를 고려하지 않았다.

연산을 통해 만들어지는 수가 중복 될 수 있음이 명확하지만 이를 고려하지 않았다. 방문 배열을 통해 이전에 만들어진 수 인지 확인해야한다.

from sys import stdin
from collections import deque

readline = stdin.readline


def get_min_command():
    init, target = map(int, readline().split())
    q = deque()
    visited = [False] * 10000
    q.append(['', init])
    visited[init] = True
    while q:
        c, n = q.popleft()
        visited[n] = True
        if n == target:
            return c

        dn = (n * 2) % 10000
        sn = n - 1 if n != 0 else 9999
        ln = int(n % 1000 * 10 + n / 1000)
        rn = int(n % 10 * 1000 + n // 10)
        if dn == target:
            return c + "D"
        if sn == target:
            return c + "S"
        if ln == target:
            return c + "L"
        if rn == target:
            return c + "R"

        if not visited[dn]:
            visited[dn] = True
            q.append([c + "D", dn])

        if not visited[sn]:
            visited[sn] = True
            q.append([c + "S", sn])

        if not visited[ln]:
            visited[ln] = True
            q.append([c + "L", ln])

        if not visited[rn]:
            visited[rn] = True
            q.append([c + "R", rn])


if __name__ == "__main__":
    T = int(readline().strip())
    for _ in range(T):
        print(get_min_command())