[백준알고리즘] 9019번: DSLR -Python

[백준알고리즘] 9019번: DSLR -Python

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

9019번: DSLR

이번 문제도 주어진 두 값 A, B 간의 제시된 4가지 이동 방법에 따라 만날 수 있는 최소 경로를 구하는 문제이다.

 

하지만 이번 문제는 이전에 많이 풀었던 길이를 구하는 문제와 달리 경로를 직접 구해야 한다.

 

따라서 최소 경로를 구하기 위해서 BFS를 이용하면서 계속해서 현재 위치와 함께 현재까지의 경로를 같이 넘겨주면서 진행하도록 했다.

 

여기서 확인해야 할 점은 두가지가 있다.

1. 1에 대해 L과 R 명령어를 실행한 결과
2. L과 R 명령어에 해당하는 동작을 수행할 때 처리방법

1번부터 확인을 하자면 1에다가 L과 R을 각각 실행한 결과는 1, 1이 아닌 10, 1000이 된다. 처음부터 1을 0001로 보고 진행하는 것과 같다.

 

1번에 대해서 저러한 결과가 나온다면 문자열로 만들고 처리할 생각을 할지도 모른다.

나도 처음에 deque(str(A))로 문자 리스트로 만든 후 deque()의 rotate() 메서드를 이용해 R의 경우 rotate(1), L의 경우 rotate(-1)하려 했다. 각각에 대해 int(''. join(deque))까지 하면 얼마나 깔끔한가.

 

그런데 이러한 방식은 시간초과에 걸린다. 애초에 고친 방법도 PyPy로 겨우 통과했고 현재 Python으로 통과한 코드는 하나 등록돼있다. 문자열을 다뤄서 회전시키는 방법은 deque이 아닌 string의 indexing으로 푼 코드를 하나 보기는 했으나, 대부분이 수식을 이용해 문제를 해결했다.

 

나도 수식을 이용해서 회전을 처리했다. L의 경우에는 현재가 4자리 수인지에 따라서 다르게 처리했고, R의 경우에는 현재가 1자리 수인지에 따라서 다르게 처리했다.

 

import sys
from collections import deque

def bfs():
    queue = deque([(first, '')])
    visited[first] = 1

    while queue:
        now, cmd = queue.popleft()
        if now == last:
            return cmd

        l_now = len(str(now))

        t = (now*2)%bound
        if not visited[t]:
            visited[t] = 1
            queue.append((t, cmd + 'D'))
            
        t = (now-1)%bound
        if not visited[t]:
            visited[t] = 1
            queue.append((t, cmd + 'S'))

        if l_now != 4:
            t = now*10
        else:
            t, d = divmod(now, 10**(l_now-1))
            t += (d*10)
        if not visited[t]:
            visited[t] = 1
            queue.append((t, cmd + 'L'))

        if l_now == 1:
            t = now*1000
        else:
            t, d = divmod(now, 10)
            t += (d*1000)
        if not visited[t]:
            visited[t] = 1
            queue.append((t, cmd + 'R'))
        

testcase = int(sys.stdin.readline())
bound = 10000
for _ in range(testcase):
    first, last = map(int, sys.stdin.readline().split())
    visited = [0]*bound
    print(bfs())

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다