DSLR

• BFS로 최단 경로를 찾고, 기본적인 경로추적을 적용해서 경로를 출력하는 문제.
• 각 숫자가 노드가 되므로 노드는 총 10000개, 한 숫자에서 변환 방법이 4가지이므로 엣지는 4*10000 개. BFS로 풀면 O(40000)수준이므로 별 문제가 되지는 않아야 한다.
• 하지만, python으로 통과하기가 꽤나 힘든데, 테스트 케이스가 상당히 많이 들어있는 것 같다. 평범하게 짠 코드로는 python3으로는 시간 초과, pypy로도 5360ms나 걸려서 통과되었다.
• 시간을 단축시키기 위해서 여러가지로 애를 쓴 결과, python으로 13704ms에 통과시키는 데에 성공했다..
  • 튜플 생성을 최대한 줄인다 → 도달한 각 숫자에 대해서 기존 숫자와 명령을 튜플로 저장하는 대신에, 기존 숫자만 리스트에 저장하고, 나중에 출력할때에 명령을 다시 계산해서 찾는다. 불필요한 작업이 추가되는 것 같지만 이 편이 속도가 빠르다.
  • 각 숫자에서 변환될수 있는 다음 숫자들의 테이블을 모든 숫자에 대해서 처음에 계산해두고 계속 재활용해서 사용한다
  • 4가지 변환을 처리하는 부분을 for문으로 처리하는 대신, 그냥 비슷한 구문을 4번 반복해서 작성했다. 속도 차이가 꽤나 난다
  • 가장 빠른 코드는 이 문제를 3004ms에 통과했다. 메모리 사용량도 평범하다. 이것은 내 로직을 쥐어짜서 최적화 한다고 해서 도달할수 있는 레벨이 아니고 뭔가 새로운 아이디어가 들어갔을 것 같은데, 코드 공개가 되어있지 않아서 확인이 불가능하다. 매우 궁금하다..

"""Solution code for "BOJ 9019. DSLR".

- Problem link: https://www.acmicpc.net/problem/9019
- Solution link: http://www.teferi.net/ps/problems/boj/9019

Tags: [BFS]
"""

import collections
import sys


def bfs(source, sink):
    deq = collections.deque([source])
    prev_state_and_cmd = [None] * 10000
    while True:
        n = deq.popleft()
        next_states = [('D', n * 2 % 10000),
                       ('S', n - 1 if n > 0 else 9999),
                       ('L', n % 1000 * 10 + n // 1000),
                       ('R', n % 10 * 1000 + n // 10)]
        for cmd, v in next_states:
            if prev_state_and_cmd[v] is None:
                prev_state_and_cmd[v] = (n, cmd)
                if v == sink:
                    return prev_state_and_cmd
                deq.append(v)        


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        prev_state_and_cmd = bfs(A, B)
        cur = B
        cmds = []
        while cur != A:
            cur, cmd = prev_state_and_cmd[cur]
            cmds.append(cmd)
        print(''.join(reversed(cmds)))


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 9019. DSLR".

- Problem link: https://www.acmicpc.net/problem/9019
- Solution link: http://www.teferi.net/ps/problems/boj/9019

Tags: [BFS]
"""

import collections
import sys


def bfs(source, sink, next_states):
    deq = collections.deque([source])
    prev = [None] * 10000
    while True:
        n = deq.popleft()
        d, s, l, r =  next_states[n]
        if prev[d] is None:
            prev[d] = n
            deq.append(d)
        if prev[s] is None:
            prev[s] = n
            deq.append(s)
        if prev[l] is None:
            prev[l] = n
            deq.append(l)
        if prev[r] is None:
            prev[r] = n
            deq.append(r)
        if prev[sink] is not None:
            return prev


def main():
    next_states = [[n * 2 % 10000,
                    (n - 1) % 10000,
                    n % 1000 * 10 + n // 1000,
                    n % 10 * 1000 + n // 10] for n in range(10000)]   
    T = int(sys.stdin.readline())
    for _ in range(T):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        prev_states = bfs(A, B, next_states)
        cur = B
        cmds = []
        while cur != A:
            prev = prev_states[cur]
            cmd = next_states[prev].index(cur)
            cmds.append('DSLR'[cmd])            
            cur = prev
        print(''.join(reversed(cmds)))


if __name__ == '__main__':
    main()