BaekJoon 9019번 : DSLR (python)

BaekJoon 9019번 : DSLR (G4 20.786%)

DSLR 문제

bfs를 이용한 최단거리 문제 + 역추적 조건이 달린 문제이다.
다른 문제들에 비해 시간 제한이 까다로운 문제라서 정답률이 상당히 낮은 것 같다.

• 각 D,S,L,R의 x를 변형하는 조건이 다르기 때문에 이 부분에서의 점화식만 잘 생각하면 될 것 같았다.
• D는 기본적으로 x를 2배 하고 10000으로 나눈 나머지 값으로 정의할 수 있고, S는 x가 0이 아닐시에 (x-1) 0일시에는 9999라고 정의할 수 있다. L과 R은 기본적으로 몫과 나머지를 이용하여 4자리수로 변경해줄 수 있는데 이 부분에서 몫과 나머지를 이용하지 못하고 조금이라도 계산이 추가되거나 시간복잡도를 가지는 연산을 추가할 경우 시간 제한에 걸리는 것 같았다.
• 기본 BFS 문제처럼 조건에 부합할 경우 q.append(nx)를 해주게 되고 index 역추적 배열 trace와 문자 역추적 배열 order를 업데이트를 해주게 된다.
• BFS가 끝났을 때 b부터 시작하여 b = trace[b]를 통해 index 역추적을 하게 되고 해당 인덱스에 order값을 넣어줌으로써 어떤 계산을 하였는지의 역추적이 가능하게 된다.

느낀점

크게 까다로운 문제는 아니었지만 제일처음에 'L'과 'R'연산을 최적화 하지 못해서 시간초과가 걸리는 문제점이 있었고 이후로는 'S'의 조건에서 x가 0일시에는 9999인데 (x-1)가 0일시에 9999라는 조건을 달아버려서 한 차례 틀리게 되었다.
이런 정답률이 낮은 문제를 만났을 때는 문제의 까다로운 조건을 더 자세히 봐야할 필요가 있다. 항상 해당 문제의 유형과 시간복잡도를 예상하는 연습을 꼭 해야 될 것 같다.

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

def bfs(a,b) :
    q = deque()
    q.append(a)
    check = [False]*(10001)
    check[a] = True
    while q :
        x = q.popleft()
        if x == b :
            break

        nx = (2*x)%10000
        if not check[nx] :
            q.append(nx)
            trace[nx] = x
            order[nx] = 'D'
            check[nx] = True

        nx = 9999 if x == 0 else x-1
        if not check[nx] :
            q.append(nx)
            trace[nx] = x
            order[nx] = 'S'
            check[nx] = True
        
        nx = (x%1000)*10 + x//1000
        if not check[nx] :
            q.append(nx)
            trace[nx] = x
            order[nx] = 'L'
            check[nx] = True
         
        nx = (x%10)*1000 + x//10
        if not check[nx] :
            q.append(nx)
            trace[nx] = x
            order[nx] = 'R'
            check[nx] = True

T = int(input())
for _ in range(T) :
    trace = [-1]*(10001)
    order = [0]*(10001)
    a, b = map(int,input().split())
    bfs(a,b)
    s = ''
    while a != b :
        s += order[b]
        b = trace[b]
    print(s[::-1])

짧게 개선된 코드

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

def bfs(a,b) :
    q = deque()
    q.append(a)
    check = [False]*(10001)
    check[a] = True
    while q :
        x = q.popleft()
        if x == b :
            break
        
        operation = [
            ((2*x)%10000, 'D'),
            (x-1 if x>0 else 9999, 'S'),
            ((x%1000)*10 + x//1000, 'L'),
            ((x%10)*1000 + x//10, 'R')
        ]

        for nx, op in operation :
            if not check[nx] :
                q.append(nx)
                trace[nx] = x
                order[nx] = op
                check[nx] = True

T = int(input())
for _ in range(T) :
    trace = [-1]*(10001)
    order = [0]*(10001)
    a, b = map(int,input().split())
    bfs(a,b)
    s = ''
    while a != b :
        s += order[b]
        b = trace[b]
    print(s[::-1])