BOJ 9019. [Gold4] DSLR

[hojongs]

Problem link

https://www.acmicpc.net/problem/9019

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

BFS, Queue
D: Double
S: Subtraction
L: Left shift
R: Right shift

A -> B로 가는 최소 명령어 배열

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

최단거리를 탐색하기 위해 BFS.
불필요한 탐색을 줄이기 위한 아이디어는 모르겠다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys
from collections import deque

readl = sys.stdin.readline

def f():
    # BFS. 큐에 초기값 저장
    queue = deque(
        [
            (a, "D"),
            (a, "S"),
            (a, "L"),
            (a, "R"),
        ]
    )
    visited = [False] * 10_001
    visited[a] = True

    # loop queue
    while len(queue) > 0:
        # curr, cmds = pop() # 마지막 명령어를 적용해야 함
        curr, cmds = queue.popleft()
        # nxt = curr + cmds[-1]
        if cmds[-1] == "D":
            nxt = (curr * 2) % 10_000
        elif cmds[-1] == "S":
            nxt = (curr - 1) % 10_000
        elif cmds[-1] == "L":
            nxt = (curr * 10 % 10_000) + (curr // 1_000)
        else:
            nxt = (curr // 10) + (curr % 10 * 1_000)
        # print(curr, cmds, nxt, visited[nxt])

        # if nxt == b: break with cmds
        if nxt == b:
            print(''.join(cmds))
            break
        # elif nxt is not visited:
        elif not visited[nxt]:
            visited[nxt] = True
            # for nxt_cmd in DSLR
            for nxt_cmd in "DSLR":
                # push (nxt, cmds + nxt_cmd) to queue
                queue.append((nxt, cmds + nxt_cmd))

t = int(readl())
for _ in range(t):
    a, b = map(int, readl().split())
    f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

https://velog.io/@kms9887/BOJ-9019-DSLR

생각해보니 숫자는 0~9999까지 고정이고, 각 수마다 함수 적용 결과는 같다.

시간 최적화를 위한 DP 아이디어? 여러 가지 테스트 케이스를 실행하므로 활용할 수 있다

f(num, cmd)의 결과는 모든 테스트 케이스에 대하여 동일하다

구현력: 알고리즘을 신속, 정확하게 구현했는가?

실패 코드의 원인

                queue.append((nxt, cmds + [nxt_cmd]))

list + list 연산은 str + str의 연산보다 더 느렸다

https://stackoverflow.com/a/64381688/12956829

# O(n)
list.copy()
list[:]
list()

https://stackoverflow.com/a/37133870/12956829

str concatenation (str1 + str2)도 time complexity는 O(n)으로 동일하지만, list의 연산값이 더 큰 듯하다

[hojongs]

시간 제한은 6초이고 수행 시간이 13초인데 통과한 게 이상함 (보정이 너무 심한듯)
나중에 Python 말고 Go로 풀어보자 (동일한 알고리즘을)

https://velog.io/@kms9887/BOJ-9019-DSLR

아래 코드와 시간 차이가 크게 나는 이유는?

https://chelseashin.tistory.com/64

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

def bfs(start, end):
    Q = deque([(start, '')])
    visited = [0] * 10000
    visited[start] = 1
    while Q:
        num, temp = Q.popleft()

        if num == end:       # 목표 숫자에 도달하면 리턴
            return temp
        # D
        if not visited[num*2 % 10000]:
            visited[num*2 % 10000] = 1
            Q.append((num*2 % 10000, temp+"D"))
        # S
        if not visited[(num-1) % 10000]:
            visited[(num-1) % 10000] = 1
            Q.append(((num-1) % 10000, temp+"S"))
        # L
        if not visited[num % 1000 * 10 + num//1000]:
            visited[num % 1000*10 + num//1000] = 1
            Q.append((num % 1000*10 + num//1000, temp+"L"))
        # R
        if not visited[num % 10*1000 + num//10]:
            visited[num % 10*1000 + num//10] = 1
            Q.append((num % 10*1000 + num//10, temp+"R"))

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