[BOJ][Python]9019번 풀이

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

9019번: DSLR

from collections import deque
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    a,b = input().split()
    b = '0'*(4-len(b)) + b
    visited = [0 for _ in range(10000)]
    q = deque([(a,'')])
    visited[int(a)] = 1
    while q:
        tmp = q.popleft()
        tmp1 = '0'*(4-len(tmp[0])) + tmp[0]
        if tmp1 == b:
            ans = tmp[1]
            break
        else:
            d = int(tmp1)*2%10000
            if visited[d] == 0:
                q.append((str(d),tmp[1]+'D'))
                visited[d] = 1
            s = int(tmp1)-1 if int(tmp1)-1 >= 0 else 9999
            if visited[s] == 0:
                q.append((str(s),tmp[1]+'S'))
                visited[s] = 1
            l = tmp1[1:]+tmp1[0]
            if visited[int(l)] == 0:
                q.append((l,tmp[1]+'L'))
                visited[int(l)] = 1
            r = tmp1[3]+tmp1[0:3]
            if visited[int(r)] == 0:
                q.append((r,tmp[1]+'R'))
                visited[int(r)] = 1
    print(ans)

착안만 한다면 코드 작성은 문제가 시키는대로 하면 되는 문제라 난이도가 어렵지는 않습니다만, 최적화가 조금 문제일 것 같네요. 빨리 푸신 분들과 비교하면 정말 어마어마하게 소요 시간 차이가 나다보니 아직 훨씬 효율적이게 할 수 있는 부분이 있는 것 같습니다.

 

문제 접근은 bfs입니다. 저는 무조건 수행해야 하는 명령이 여러 개 있으면서 최소한으로 끝낼 수 있는 법을 묻는 문제라서 바로 bfs겠구나 라는 추측을 했습니다. 결과적으로 맞는 추측이었던 것 같구요. 사실 bfs문제를 많이 풀어보신 분이라면 바로 직감이 오셨을 것 같습니다. 저같은 경우도 class 3을 풀면서 정말 많은 그래프 탐색 문제, 특히 bfs만을 써야하거나 bfs를 썼을 때 효율적인 문제들이 많이 포진되어 있는 것을 느꼈습니다(70퍼센트는 bfs문제가 아닌가 싶은 느낌이었네요). 그런 경험이 쌓였던 것인지 구현스럽지만 본질은 bfs인 문제들을 보는 눈이 아주 약간은 길러졌다고 해도 과언이 아닐 것 같네요. 위에서도 말씀을 드렸지만 해당 문제가 bfs를 이용하면 되겠구나 라는 것을 눈치만 채신다면 문제에서 시키는대로만 하면 바로 풀리는 문제입니다(최적화는 별개지만). 다만 언어의 특성 때문일수도 있습니다(파이썬의 경우 상당히 편하게 문자열과 정수를 왔다갔다 할 수 있기 때문). 주의하셔야 할 부분은 S 명령어의 부분일까요. 저는 -1만 생각하고 풀다가 제대로 안풀리는 경우가 있었습니다. n이 0일 때 S를 사용하면 n이 -1이 되면서 9999로 바꾸어야 한다는 점(레지스터의 범위가 0~9999이기 때문)이 명시가 되어있으니 놓치지 않으시길 바랍니다.