Sign in Subscribe
PS

[PS] BOJ 9019 / DSLR

Minjun Kim

• 5 min read
[PS] BOJ 9019 / DSLR
문제 링크: https://www.acmicpc.net/problem/9019
Thumbnail: Photo by Kyle Loftus (Unsplash)

그래프 탐색을 이용하는 문제입니다. 다만, 생각보다 시간과 메모리 초과로 고전했습니다 ㅎㅎ;

풀이

기본적인 접근 방법은 그래프 탐색 (DFS, BFS)입니다. 사용 가능한 4가지 연산을 활용해 \(A\)를 \(B\)로 변환하는 최소 길이의 명령어를 찾아야 합니다. 즉, 그래프 탐색을 통해 답을 찾아낸 뒤, 그 답에 도달한 경로를 출력하면 됩니다.

BFS

이번 문제는 BFS를 사용해 풀었습니다. 먼저 BFS의 기본 구문을 다시 복습해봅시다.

A, B = map(int, input().split())

# BFS
queue = deque([A])
prev = [0] * 10000
prev[A] = A
while queue:
    cur_number = queue.popleft()
    for cmd in (D, S, L, R):
        next_number = cmd(cur_number)
        if next_number == B:    # 정답을 찾았다면 즉시 종료.
            break
        queue.append(next_number)

BFS의 기본 구현

큐에 방문할 원소들을 넣고, 다시 하나씩 꺼내가며 목표값인 \(B\)를 찾을 때 까지 반복하는게 BFS입니다. 이때, 방문할 다음 노드를 결정하기 위한 4가지 명령어인 D, S, L, R을 구현해야 합니다.

def D(number):
    """number을 두 배로 바꿉니다. 이때, 10000을 넘어갈 경우 10000으로 나눈 나머지가 number가 됩니다."""
    return (number * 2) % 10000

def S(number):
    """number을 1 감소시킵니다. 이때, 기존 number가 0이었다면 9999로 바꿉니다."""
    return (number + 9999) % 10000

def L(number):
    """n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다."""
    return number // 1000 + number % 1000 * 10

def R(number):
    """n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다."""
    return number // 10 + number % 10 * 1000

DSLR 명령어 구현

BFS 최적화 - 중복 방문 배제하기

이제 BFS를 최적화해야 합니다. 당연하게도, 그냥 단순히 위 코드로 제출하게 되면 시간 초과를 맞이하게 됩니다.

BFS를 진행하다 보면, 이전에 방문한 노드를 다시 방문하게 될 수 있습니다. 이 경우 사이클이 발생하며, 이러한 경로는 최단경로가 아님을 쉽게 알 수 있습니다.

따라서, 중복 방문을 배제하기 위해 방문 정보를 기록해야 합니다.

A, B = map(int, input().split())

# BFS
queue = deque([A])
visited = [0] * 10000
visited[A] = 1
while queue:
    cur_number = queue.popleft()
    for cmd in (D, S, L, R):
        next_number = cmd(cur_number)
        if visited[next_number] == 0:    # 같은 숫자로 다시 돌아오는 경우는 사이클이 형성된 것. 이후의 탐색이 효율적인 경로가 아님이 자명함.
            visited[next_number] = 1
            if next_number == B:    # 정답을 찾았다면 즉시 종료.
                break
            queue.append(next_number)

역추적

이제 정답 명령어를 출력해야 합니다. BFS를 진행하면서 진행 과정을 함께 큐에 기록할 수도 있으나, 메모리를 낭비하게 됩니다. 따라서, BFS로 탐색한 경로를 역추적하는 방식을 사용했습니다.

기존에 탐색 여부를 기록하던 배열인 visited대신, 해당 노드 이전에 방문했던 노드를 기록할 배열 prev를 사용합니다.

BFS에 다음에 방문할 노드를 큐에 넣는 과정에서, prev에 다음 탐색할 노드(next_number)에 대한 정보를 추가합니다. 이때, 해당 노드 이전에 방문했던 노드(cur_number)와 해당 노드를 방문하기 위해 수행한 명령어(cmd.__name__) 를 기록합니다.

A, B = map(int, input().split())

# BFS
queue = deque([A])
prev = [0] * 10000
prev[A] = A
while queue:
    cur_number = queue.popleft()
    for cmd in (D, S, L, R):
        next_number = cmd(cur_number)
        if prev[next_number] == 0:    # 같은 숫자로 다시 돌아오는 경우는 사이클이 형성된 것. 이후의 탐색이 효율적인 경로가 아님이 자명함.
            prev[next_number] = (cur_number, cmd.__name__)
            if next_number == B:    # 정답을 찾았다면 즉시 종료.
                break
            queue.append(next_number)

BFS 탐색 경로 기록

이후, 역추적을 통해 \(A\)에서 \(B\)까지의 명령어를 출력해야 합니다. 이름처럼 거꾸로 추적하므로, 결과를 출력할 때는 뒤집어야 합니다.

stack = []
while B != A:
    B, cmd = prev[B]
    stack.append(cmd)
print("".join(stack[::-1]))

결과 출력

전체 코드

from collections import deque
input = open(0).readline

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

def S(number):
    return (number + 9999) % 10000

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

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

for _ in range(int(input())):   # 각각의 테스트 케이스에 대해 연산 수행
    A, B = map(int, input().split())

    # BFS
    queue = deque([A])
    prev = [0] * 10000
    prev[A] = A
    while queue:
        cur_number = queue.popleft()
        for cmd in (D, S, L, R):
            next_number = cmd(cur_number)
            if prev[next_number] == 0:    # 같은 숫자로 다시 돌아오는 경우는 사이클이 형성된 것. 이후의 탐색이 효율적인 경로가 아님이 자명함.
                prev[next_number] = (cur_number, cmd.__name__)
                if next_number == B:    # 정답을 찾았다면 즉시 종료.
                    break
                queue.append(next_number)
    
    # 경로 출력
    stack = []
    while B != A:
        B, cmd = prev[B]
        stack.append(cmd)
    print("".join(stack[::-1]))

solution.py