[9019] DSLR

백트래킹 이용 없이 1

import sys
from collections import deque

input = sys.stdin.readline


def D(n):
    return (n * 2) % 10000


def S(n):
    return (n - 1) % 10000


def L(n):
    return (n % 1000 * 10) + (n // 1000)


def R(n):
    return (n // 10) + ((n % 10) * 1000)


T = int(input())
while T:
    start, goal = map(int, input().split())

    # 정답 변수 초기화
    cnt = sys.maxsize
    answer = ""

    # bfs
    # 큐에 일단 기본 입력값 넣음
    # 근데 길이도 알아야 하니까 (값, 길이)로 넣기
    q = deque([(start, "")])
    visited = [False] * 10001
    visited[start] = True
    while q:
        now, idx = q.popleft()
        # 큐에 들어 온 값이 목표값이랑 같은가?
        if now == goal:
            print(idx)
            break
        # 큐에 넣기
        nxt = D(now)
        if not visited[nxt]:
            q.append((nxt, idx + "D"))
            visited[nxt] = True
        nxt = S(now)
        if not visited[nxt]:
            q.append((nxt, idx + "S"))
            visited[nxt] = True
        nxt = L(now)
        if not visited[nxt]:
            q.append((nxt, idx + "L"))
            visited[nxt] = True
        nxt = R(now)
        if not visited[nxt]:
            q.append((nxt, idx + "R"))
            visited[nxt] = True
    T -= 1

 

위 코드에서 함수 없이

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())
while T:
    start, goal = map(int, input().split())
    # bfs
    # 큐에 일단 기본 입력값 넣음
    # 근데 길이도 알아야 하니까 (값, 길이)로 넣기
    q = deque([(start, "")])
    visited = [False] * 10001
    visited[start] = True
    while q:
        now, idx = q.popleft()
        # 큐에 들어 온 값이 목표값이랑 같은가?
        # 그럼 정답변수랑 비교했을 작은 값 갱신해서 저장 후 종료하기
        if now == goal:
            print(idx)
            break
        # 큐에 넣기
        nxt = (now * 2) % 10000
        if not visited[nxt]:
            q.append((nxt, idx + "D"))
            visited[nxt] = True
        nxt = (now - 1) % 10000
        if not visited[nxt]:
            q.append((nxt, idx + "S"))
            visited[nxt] = True
        nxt = (now % 1000 * 10) + (now // 1000)
        if not visited[nxt]:
            q.append((nxt, idx + "L"))
            visited[nxt] = True
        nxt = (now // 10) + ((now % 10) * 1000)
        if not visited[nxt]:
            q.append((nxt, idx + "R"))
            visited[nxt] = True
    T -= 1

 

백트래킹 사용

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())
while T:
    start, goal = map(int, input().split())
    # bfs
    q = deque([start])
    parent = [-1] * 10000
    command = [""] * 10000
    visited = [False] * 10000
    visited[start] = True
    while q:
        now = q.popleft()
        # 큐에 들어 온 값이 목표값이랑 같은가?
        if now == goal:
            res = []
            while now != start:
                res.append(command[now])
                now = parent[now]
            print("".join(reversed(res)))
            break
        # 큐에 넣기
        nxt = (now * 2) % 10000
        if not visited[nxt]:
            q.append(nxt)
            visited[nxt] = True
            parent[nxt] = now
            command[nxt] = "D"
        nxt = (now - 1) % 10000
        if not visited[nxt]:
            q.append(nxt)
            visited[nxt] = True
            parent[nxt] = now
            command[nxt] = "S"
        nxt = (now % 1000 * 10) + (now // 1000)
        if not visited[nxt]:
            q.append(nxt)
            visited[nxt] = True
            parent[nxt] = now
            command[nxt] = "L"
        nxt = (now // 10) + ((now % 10) * 1000)
        if not visited[nxt]:
            q.append(nxt)
            visited[nxt] = True
            parent[nxt] = now
            command[nxt] = "R"
    T -= 1