DSLR

solved_ac[Class3][DSLR](https://www.acmicpc.net/problem/9019)

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다

• 예제 입력 1

3
1234 3412
1000 1
1 16

• 예제 출력 1

LL
L
DDDD

BFS

사용 이유

이 문제를 보고 [그래프]화 할 수 있냐가 제일 중요하다고 생각한다. 사실 문제를 그래프화 하기만 한다면 BFS를 떠올리는 것은 쉽다. 결국 묻는 것은 "출발 노드에서 목적 노드까지의 최단 거리"이기 때문이다. 나는 이전에 이와 비슷한 문제를 경험해보아서 덕분에 떠올릴 수 있었다.

숨바꼭질2

CODE

1트 (메모리 초과)

import sys
from collections import deque
input = sys.stdin.readline

# 명령어 D
def D_command(n):
    n = int(n)
    if 2*n > 9999:
        return str(2*n % 10000).zfill(4)
    else:
        return str(2*n).zfill(4)

# 명령어 S
def S_command(n):
    n = int(n)
    if n == 0:
        return 9999
    else:
        return str(n-1).zfill(4)

# 명령어 L
def L_command(n):
    temp = deque(list(str(n)))
    temp.append(temp.popleft())
    return "".join(temp).zfill(4)

# 명령어 R
def R_command(n):
    temp = deque(list(str(n)))
    temp.appendleft(temp.pop())
    return "".join(temp).zfill(4)

# Queue 안에 목표 숫자가 있는지 체크
def check_q(q,num):
    for i in range(len(q)):
        if num == q[i][0]:
            return q[i][1]
    return False


def bfs(start,end):
    q = deque([[start,""]])
    
    while q:
        cur_node, path = q.popleft()
        next_q = [[D_command(cur_node),path+"D"], [S_command(cur_node),path+"S"] ,[L_command(cur_node),path+"L"],[R_command(cur_node),path+"R"]]
        flag = check_q(next_q,end)
        if flag:
            return flag
        q.extend(next_q)

for _ in range(int(input())):
    a,b = input().split()
    a = a.zfill(4)
    b = b.zfill(4)

    print(bfs(a,b))

시간초과를 고려하여 check_q 함수를 사용할 때, 전체 큐를 검사하는 것이 아닌 확장 큐에 대해서만 검사를 해주었다.

하지만 메모리 초과에 걸려 실패 ㅠ_ㅠ

2트 (시간 초과)

import sys
from collections import deque
input = sys.stdin.readline

# 명령어 D
def D_command(n):
    n = int(n)
    if 2*n > 9999:
        return str(2*n % 10000).zfill(4)
    else:
        return str(2*n).zfill(4)

# 명령어 S
def S_command(n):
    n = int(n)
    if n == 0:
        return 9999
    else:
        return str(n-1).zfill(4)

# 명령어 L
def L_command(n):
    temp = deque(list(str(n)))
    temp.append(temp.popleft())
    return "".join(temp).zfill(4)

# 명령어 R
def R_command(n):
    temp = deque(list(str(n)))
    temp.appendleft(temp.pop())
    return "".join(temp).zfill(4)

def bfs(start,end):
    q = deque([[start,""]])
    visited = [start]
    while q:
        cur_node, path = q.popleft()
        D_next_node = D_command(cur_node)
        S_next_node = S_command(cur_node)
        L_next_node = L_command(cur_node)
        R_next_node = R_command(cur_node)

        # Search
        if D_next_node == end:
            return path+"D"
        if S_next_node == end:
            return path+"S"
        if L_next_node == end:
            return path+"L"
        if R_next_node == end:
            return path+"R"

        # 다음 Breadth
        if D_next_node not in visited:
            q.append([D_next_node,path+"D"])
            visited.append(D_next_node)
        if S_next_node not in visited:
            q.append([S_next_node,path+"S"])
            visited.append(S_next_node)
        if L_next_node not in visited:
            q.append([L_next_node,path+"L"])
            visited.append(L_next_node)
        if R_next_node not in visited:
            q.append([R_next_node,path+"R"])
            visited.append(R_next_node)
    

for _ in range(int(input())):
    a,b = input().split()
    a = a.zfill(4)
    b = b.zfill(4)

    print(bfs(a,b))

BFS 진행 과정 그림의 빨간 동그라미를 보면 간선이 2개 이상인 것을 볼 수 있다. 즉, 중복 값이 있다는 건데

노드 방문 체크를 하지 않으면 이처럼 불필요한 계산이 발생되어 시간이 더 많이 걸리게 된다. 따라서 visited 배열을 생성하여 이미 방문했던 노드면 더 방문 하지 않도록 설정하였다.

그러나 결과는 또 다시 시간 초과 ...

3트(정답)

import sys
from collections import deque
input = sys.stdin.readline

# 명령어 D
def D_command(n):
    D_n = 2*n
    if D_n> 9999:
        return D_n % 10000
    else:
        return D_n

# 명령어 S
def S_command(n):
    if n == 0:
        return 9999
    else:
        return n-1

# 명령어 L
def L_command(n):
    L_n = n%1000 * 10 + n//1000
    return L_n

# 명령어 R
def R_command(n):
    R_n = n%10 * 1000 + n//10
    return R_n

def bfs(start,end):
    q = deque([[start,""]])
    visited = [False]*10000
    while q:
        cur_node, path = q.popleft()
        D_next_node = D_command(cur_node)
        S_next_node = S_command(cur_node)
        L_next_node = L_command(cur_node)
        R_next_node = R_command(cur_node)

        # Search
        if D_next_node == end:
            return path+"D"
        if S_next_node == end:
            return path+"S"
        if L_next_node == end:
            return path+"L"
        if R_next_node == end:
            return path+"R"

        # 다음 Breadth
        if not visited[D_next_node]:
            q.append([D_next_node,path+"D"])
            visited[D_next_node] = True
        if not visited[S_next_node]:
            q.append([S_next_node,path+"S"])
            visited[S_next_node] = True
        if not visited[L_next_node]:
            q.append([L_next_node,path+"L"])
            visited[L_next_node] = True
        if not visited[R_next_node]:
            q.append([R_next_node,path+"R"])
            visited[R_next_node] = True
    

for _ in range(int(input())):
    a,b = map(int,input().split())

    print(bfs(a,b))

2트 코드와 비교해보았을 때 명령어 L,R의 작동방식이 달라졌다.

• <2트 명령어 L,R 작동 방식>

• <3트 명령어 L,R 작동 방식>

단순 계산 (Left, Right 결과값은 코드 참조)

아무래도 함수를 사용하는 것보다 계산한 결과를 바로 return 해주는 것이 더욱 빠른 시간 안에 구할 수 있기 때문인듯 싶다.

고찰

문제의 Logic 자체는 크게 어렵지 않았는데 [시간초과, 메모리초과]를 피하는 것이 어려웠다.

심지어 Python3로 통과하기가 쉽지 않아서 PyPy3로 돌렸다..