[백준 9019 파이썬] DSLR (골드 5, BFS)

알고리즘 유형 : BFS
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

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


# 숫자 연산을 활용하여 DSLR 변환 결과값 구하기
# L, R의 경우에는 문자열 형태보다 숫자 연산으로
# 구하는게 시간복잡도 측면에서 이득
def cal(n):
    yield ("D", (n * 2) % 10000)
    yield ("S", (n + 9999) % 10000)
    yield ("L", (n*10)%10000 + (n*10//10000))
    yield ("R", (n+10000)//10 + (n%10)*1000 - 1000)


T = int(input())

for _ in range(T):
    A, B = map(int, input().split())
    path = [""]*10001 # 최단경로 역추적 리스트
    
    q = deque()
    q.append(A)
    
    # 최단경로 원소 유무로 탐색 여부를 판단하므로
    # 출발 노드의 최단경로도 어떤 값으로 초기화해두기
    path[A] = "start"
    
    while q:
        n = q.popleft()
        if n == B:
            print(path[B][5:]) # start 빼고 출력
            break
        
        for cmd, res in cal(n):
            if path[res]:
                continue
            
            path[res] = path[n] + cmd
            q.append(res)

풀이 요약

1. 이 문제는 pypy3로 제출해야 통과된다. python3으로 제출한 현황을 보니 정답자가 6명밖에 없던데, 그냥 pypy3로 AC 받은걸로 만족해야겠다..

2. BFS에 최단경로 역추적을 섞은 간단한 문제이다.

   유의할 점을 꼽자면 두 군데가 있는데,

   첫 번째는 최단경로 역추적을 하는 리스트를 방문 여부 체크 용도로도 활용하는 것이다.

   어떤 노드에 방문을 했을 때 반드시 어떤 경로 값으로 그 노드의 path 값이 초기화된다.

   즉, path[idx]에 값이 들어있으면(""가 아니면) idx를 방문한 것이고, ""이면 방문을 안한 것으로 판단해도 되는 것이다.

   두 번째는 DSLR 명령어 변환 결과값을 구할 때 int형으로만 다뤄서, 즉 숫자 연산만을 사용하여 결과값을 구함으로써 시간복잡도를 줄이는 것이다.

   문자열 형태로 형변환 후 더 쉽게 결과값을 구할 수는 있지만, 시간복잡도 측면에서 숫자 연산으로 구하는게 더 이득이다. 문자열 방식으로 해도 pypy3 기준 AC를 받을 수 있긴 하다.

3. max(S) 출력

배운 점, 어려웠던 점

• 문자열 형변환 및 슬라이싱과, 숫자 연산의 시간복잡도 차이에 대해 체감할 수 있는 문제였다.

• 최단경로 리스트를 방문 여부 리스트로 동시에 활용하는 아이디어를 떠올려본 유익한 문제였다.