Baekjoon 9019번 DSLR

💭 문제가 궁금하다면?

내가 시도한 방법

• 'A에서 B로 변환하기 위해 필요한 최소한의 명령어' => BFS가 떠올랐다.
• 어떤 명령어를 거쳐 B에 도달했는지 어떻게 저장할 지 고민을 했던 결과,
• visited에 지나온 경로를 담아서 저장하는 방식을 해보자는 결론에 도달했다!
• DSLR함수 : 명령어 D와 S의 경우 n의 범위에서 벗어날 경우를 고려해서 추가적인 작업이 필요했는데, 최대한 그런 조건을 따로 분기처리하지 않는 방법을 떠올리고 싶었다.

def DSLR(num): 
    word = f'{num:04d}' # word: L, R 작업을 위한 num을 4자리 string으로 변환
    result = {
        'D': (num * 2) % 10000,
        'S': num + 9999 - bool(num) * 10000,
        'L': int(word[1:] + word[0]),
        'R': int(word[-1] + word[:3])
    }
    return result


def bfs(start, end):
    q = ['' for _ in range(10000)]
    visited = ['' for _ in range(10000)]
    front = -1
    rear = 0
    q[rear] = start
    visited[start] = 'start'
    cnt = 0

    while front != rear:
        front += 1
        num = q[front]

        for command, new in DSLR(num).items():

            if new == end: # end(target)에 도달하면 
                return visited[num][5:] + command # 시작점 단어 'start'제외하고 출력

            if not visited[new]:
                cnt += 1
                rear += 1
                q[rear] = new
                visited[new] = visited[num] + command


T = int(input())
for _ in range(T):
    initial, target = map(int, input().split()) # initial: A, target: B
    print(bfs(initial, target))

참고

• 처음에는 while문의 종료 조건을 q에서 값을 뽑고난 후로 했다. 결과는 시간초과....
• 출력을 해보니 end까지 단계를 많이 거칠 경우, end에 도달하더라도 종료조건(q에서 pop할 때)을 만나기 전까지 다른 불필요한 작업이 진행된다는 점을 발견했다.
• 기존의 코드 형태로는 너비 우선 탐색이기 때문에 같은 레벨의 작업의 모두 끝나고 나서야 판별을 하기 때문이었다.
• 그래서 바로 for문 안으로 종료조건을 옮기니까 통과됐다...