백준 9019

문제출처: https://www.acmicpc.net/problem/9019

[수정한 답]

import sys 
from collections import deque
sys.setrecursionlimit(1000000)
sys.stdin = open("input.txt", "r")

def go(start, end):
    # 어차피 맨 처음 start에서는 how[start]가 빈칸으로 채워져 있어서 프린트 할 것 없음
    if start == end:  
        return
    go(start, fro[end])
    print(how[end], end='')

n = int(sys.stdin.readline())
for i in range(n):
    start, end = map(int, sys.stdin.readline().split())
    dist= [-1] * 10000
    fro = [-1] * 10000
    how = [''] * 10000
    check = [False] * 10000
    
    dq = deque()
    dq.append(start)
    dist[start] = 0
    check[start] = True
    while dq:
        num = dq.popleft() # 숫자
        # D
        nxt = (num*2)%10000
        **if check[nxt] == False:**
            check[nxt] = True
            dist[nxt] = dist[num] + 1
            fro[nxt] = num
            how[nxt] = 'D'
            dq.append(nxt)
        # S
        nxt = num-1
        if nxt != -1 : nxt = 9999
        if check[nxt] == False:
            check[nxt] = True
            dist[nxt] = dist[num] + 1
            fro[nxt] = num
            how[nxt] = 'S'
            dq.append(nxt)
        # L
        nxt = (num%1000)*10 + num//1000
        if check[nxt] == False:
            check[nxt] = True
            dist[nxt] = dist[num] + 1
            fro[nxt] = num
            how[nxt] = 'L'
            dq.append(nxt)
        # R   
        nxt = num%10*1000 + num//10
        if check[nxt] == False:
            check[nxt] = True
            dist[nxt] = dist[num] + 1
            fro[nxt] = num
            how[nxt] = 'R' 
            dq.append(nxt)
                
    # 정답 찾기   
    go(start, end)
    print()

[오답노트 / 느낀 점]

1. check배열의 경우 처음부터 추가 하지 않고 일일히
if dist[nxt] == -1 and fro[nxt] == -1 and how[nxt] == '' :
이런식의 조건문을 사용했었는데, check배열을 추가해서 하니 훨씬 편해짐.

2. 1번의 check 배열에 초기값에서 값이 바뀌었는지 아닌지를 체크한 뒤에 아직 초기값을 경우에만 deque에 값을 넣어주다보니 while loop 실행횟수가 줄어들어서 시간초과 문제 해결됨

3 go함수에서 프린트를 재귀함수를 통해 어떻게 처리했는 지 기억해둘 것!