DSLR

문제분석

밤 11시에 문제를 풀기 시작해서 얼른 풀고 포스팅을 끝낸 후에 자려고 했는데, 몇가지 실수들과 문제를 꼼꼼하게 읽지 않은 탓에 벌써 새벽 한시 반이 되었다.

정말 간단한, 평범한 BFS문제인 것 같은데 디테일하게 코드를 짜는 능력이 부족했던 것 같다.

이번 포스팅에서는 문제 해설이라기 보다는 내가 놓쳤던 부분들을 적어보려고 한다.

  • 먼저, 특정 숫자를 거쳐갔는지 확인&저장하는 작업이다. BFS함수 내부에 길이 10,000의 리스트를 생성해 주었다. 이 리스트에 방문 기록을 저장하며, 최초로 방문한 수에 대해서만 deque에 추가해 주었다.

  • D,S,L,R 문자를 출력하는 방식에 대해 알아보자. deque에 숫자와 함께, 그 숫자까지 오는데 사용한 명령어(DSLR)도 저장한다면 메모리를 과도하게 차지한다.(처음에 이 방법으로 했다가 메모리 초과가 발생했다.) 따라서, 위에서 생성한 리스트에 직전 숫자에서 해당 숫자로 오는데 사용한 명령어와, 직전 숫자를 저장한다. DSLR을 출력할 때는 직전 숫자를 차근차근 되짚어가며 명령어들을 수집해 출력한다.

  • 연산 L과 R을 수행할때, 문제 설명에도 나와 있듯이 항상 숫자를 네자리수로 생각하고 연산을 수행해야 한다. 1에 L을 적용하면 10, 1에 R을 적용하면 1000이 된다. 123에 R을 적용하면, 312 아니라 3012가 된다.

  • 내가 한 실수가 한가지 더 있다. 문제에서 S연산을 수행할 때, n이 0이라면 9999가 대신 레지스터에 저장된다고 했는데, n-1이 0이라면 으로 잘못 해석했었다…

위의 규칙들을 숙지하고 BFS를 사용해 코드를 구현하면 된다. python으로는 시간초과가 발생해 pypy3로 제출했다.(python으로 통과하신 분이 단 한 명이었다.)

CODE

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

def BFS(a,b):
    point=deque([a])
    dslr=list(-1 for _ in range(10_000))
    dslr[a]=[-1,-1]

    while point:
        x=point.popleft()
        if x == b:
            answer=deque([])
            while True:
                i,j=dslr[x]
                if i == -1:
                    break
                answer.appendleft(j)
                x=i
            print(''.join(answer))

        if dslr[2*x%10_000]==-1 and dslr[2*x%10_000]==-1:
            point.append(2*x%10_000)
            dslr[2*x%10_000]=[x,'D']

        if x<1 and dslr[9999]==-1:
            point.append(9999)
            dslr[9999]=[x,'S']
        elif x>=1 and dslr[x-1]==-1:
            point.append(x-1)
            dslr[x-1]=[x,'S']

        tmp1=x//1000
        tmp2=(x%1000)//100
        tmp3=(x%100)//10
        tmp4=(x%10)
        l_tmp=1000*tmp2+100*tmp3+10*tmp4+tmp1
        r_tmp=1000*tmp4+100*tmp1+10*tmp2+tmp3

        if dslr[l_tmp]==-1:
            point.append(l_tmp)
            dslr[l_tmp]=[x,'L']
        if dslr[r_tmp]==-1:
            point.append(r_tmp)
            dslr[r_tmp]=[x,'R']

for _ in range(int(read())):
    a,b=map(int,read().split())
    BFS(a,b)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]