[BOJ 9019] DSLR (Python)

풀이

처음 방문배열 없이 모든 경우의 수에 대해 큐에 집어놓고 BFS 탐색을 수행했다. 레지스터의 초기값과 최종값이 언젠가는 같아질 것이라는 생각때문에 방문 배열이 필요하지 않다고 생각하였다. 주어진 테스트 케이스는 통과했지만, 채점 결과는 시간 초과와 메모리 초과가 빈번히 발생했다.

방문 배열없이 BFS 탐색을 진행한 점과 'L'과 'R' 연산을 진행할 때 str(), list(), append(), join() 등의 문자열 처리 함수를 사용한 점이 시간 초과와 메모리 초과의 원인이었다고 생각하였고 코드를 수정했다. (백준의 질문과 다른 사람의 블로그를 보니 문자열 처리 함수에서 시간초과가 날 것이라는 글을 볼 수 있었다...) 마지막으로 문제 풀이에 대한 로직을 간략하게 설명하겠다.

1. (명령어, 레지스터의 초기값) 쌍으로 큐에 넣는다.

2. BFS 탐색을 수행한다.

   • 레지스터의 초기값과 최종값이 같다면 명령어 반환
   • 같지 않다면 D, S, L, R에 대한 연산을 수행하고, 연산된 값이 BFS 탐색을 한 적이 없다면 해당 값과 명령어를 큐에 넣는다.

3. 위 과정을 레지스터의 초기값과 최종값이 같아질 때까지 반복한다.

코드

# PyPy3, Python3 --> visited 배열 없이는 메모리 초과
# --> 그래서 visited 배열 생성 후에는 시간 초과
import sys
from collections import deque

# .zfill()
input = sys.stdin.readline
T = int(input())


def bfs(start, end, visited):
    q = deque([('', start)])
    visited[start] = True

    while q:
        command, cur = q.popleft()
        if cur == end:
            return command

        computation = (cur * 2) % 10000
        if not visited[computation]:
            visited[computation] = True
            q.append((command + 'D', computation))

        # n=0 이라면 n-1은 -1이다.
        # -1 mod 10000 = 9999 로 visited[9999]가 True 된다. --> 조건식 하나로도 충분
        computation = (cur - 1) % 10000
        if not visited[computation]:
            visited[computation] = True
            q.append((command + 'S', computation))

        computation = (cur % 1000) * 10 + cur // 1000
        if not visited[computation]:
            visited[computation] = True
            q.append((command + 'L', computation))

        computation = (cur % 10) * 1000 + cur // 10
        if not visited[computation]:
            visited[computation] = True
            q.append((command + "R", computation))


for _ in range(T):
    initial, final = map(int, input().split())
    visited = [False] * 10000

    print(bfs(initial, final, visited))