9019

날짜 : 2023. 04. 03

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque
t = int(sys.stdin.readline())  # 테스트케이스


def num(t):  # 자릿수 -> 숫자 변환
    a = str(t)
    d1, d2, d3, d4 = 0, 0, 0, 0
    if len(a) == 4:
        d1, d2, d3, d4 = a[0], a[1], a[2], a[3]
    elif len(a) == 3:
        d2, d3, d4 = a[0], a[1], a[2]
    elif len(a) == 2:
        d3, d4 = a[0], a[1]
    else:
        d4 = a[0]
    return int(d1), int(d2), int(d3), int(d4)


def bfs(a):
    queue = deque()
    queue.append([(num(a)), ""])
    visited[a] = True  # 방문처리
    global b
    while queue:
        tmp, com = queue.popleft()
        p, q, r, s = tmp
        #print(p, q, r, s, com)
        temp = (((int(p) * 10) + int(q)) * 10 + int(r)) * 10 + int(s)
        if temp == b:  # 원하는 값 도달 -> 명령어 출력
            return com
        else:
            # D연산
            if not visited[(temp * 2) % 10000]:
                visited[(temp * 2) % 10000] = True
                queue.append([num((temp * 2) % 10000), com+"D"])
            # S연산
            if temp == 0 and not visited[9999]:
                visited[9999] = True
                queue.append([(9, 9, 9, 9), com+"S"])
            else:
                if not visited[temp-1]:
                    visited[temp-1] = True
                    queue.append([num(temp-1), com+"S"])
            # L연산
            n = (((int(q) * 10) + int(r)) * 10 + int(s)) * 10 + int(p)
            if not visited[n]:
                visited[n] = True
                queue.append([(q, r, s, p), com+"L"])
            # R연산
            n = (((int(s) * 10) + int(p)) * 10 + int(q)) * 10 + int(r)
            if not visited[n]:
                visited[n] = True
                queue.append([(s, p, q, r), com+"R"])
    return


for _ in range(t):
    visited = [False] * 10000
    a, b = map(int, sys.stdin.readline().split())  # a, b 입력
    if a == b:
        print("")
    else:
        print(bfs(a))

 

 

풀이

- BFS를 활용하여 풀이한다.

- S, R연산으로 인해 각 숫자를 문자열로 파싱하는 함수를 만들고, 이를 활용하여 자릿수를 교체한다.

- 메모리, 시간초과를 대비해 중복을 제거해야 함으로 visited 리스트를 사전에 만들어 방문체크를 함으로써 불필요한 방문을 사전에 제거한다.

 

 

알게된 점

- 원리는 간단했는데 큐와 변수를 동일하게 q로 설정하여 컴파일 에러가 발생했다.

- 메모리초과가 지속적으로 발생했고, 질문을 확인해보니 이는 방문했던 수를 중복방문했기 때문이라는 것을 확인, visited 리스트를 사전에 만들어 중복방문을 방지하여 해결할 수 있었다.

- 전반적으로 방향은 얼추 맞은 것 같았지만 자잘자잘하게 간과했다는 점이 아쉬웠다.

- PS 괒어에서 자잘한 것들을 간과한다면 이또한 solve할 수 없기 때문에, 변수명, 중복 제거, 시간복잡도 등 다양하게 고려할 수 있도록 노력해야겠다.

 

 

참고 사이트

-