[백준] 9019 : DSLR (pypy3)

BFS 문제

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

---

시간 초과

1. 문자열 변환 및 조작 연산은 느리다.

• 문자열 변환
  • 문자열 변환(정수 -> 문자열 -> 정수)이 빈번하게 발생하면 누적된 비용이 상당히 커질 수 있다.
• 문자열 슬라이싱
  • 슬라이싱 연산은 새로운 문자열을 생성하는 작업이므로, 메모리 할당 및 복사가 발생하며 매우 느린 작업이다.
  • 문자열 슬라이싱의 시간 복잡도는 O(k)로 비용이 크다. 이 때, k는 슬라이스된 문자열의 길이이다.

 

문자열 코드 (시간 초과 + 오답)

while queue:
    val, dslr = queue.popleft()

    if val not in visited:
        visited.add(val)
        queue.append(((2 * val) % 10000, dslr + "D"))

        if val == 0:
            queue.append((9999, dslr + "S"))
        else:
            queue.append((val - 1, dslr + "S"))

        val = str(val)
        queue.append((int(val[1:] + val[0]), dslr + "L"))
        queue.append((int(val[-1] + val[0:-1]), dslr + "R"))

 

 

2. 불필요한 for문은 성능 저하를 초래한다.

• 코드 1에서는 루프 내부에서 네 번의 조건문 확인이 이루어지기 때문에 불필요한 반복 확인이 발생한다.
• BFS에서 많은 노드를 처리할 때 이러한 불필요한 반복 확인이 성능 저하로 이어질 수 있다.

코드1 (성공)

  while queue:
        val, dslr = queue.popleft()

        for i in range(4):
            if i == 0:  # D 명령어
                newVal = (2 * val) % 10000
            elif i == 1:  # S 명령어
                newVal = val - 1 if val > 0 else 9999
            elif i == 2:  # L 명령어
                newVal = (val % 1000) * 10 + val // 1000
            elif i == 3:  # R 명령어
                newVal = (val % 10) * 1000 + val // 10

            if newVal not in visited:
                ...

 

 

코드2 (성공)

  while queue:
        val, dslr = queue.popleft()

        # D 명령어
        newVal = (2 * val) % 10000
        if newVal not in visited:
        	...

        # S 명령어
        newVal = val - 1 if val > 0 else 9999
        if newVal not in visited:
            ...

        # L 명령어
        newVal = (val % 1000) * 10 + val // 1000
        if newVal not in visited:
            ...

        # R 명령어
        newVal = (val % 10) * 1000 + val // 10
        if newVal not in visited:
            ...

 

 

코드1과 코드2의 차이

• 위에가 코드1의 실행 결과이다.
• 확실히 불필요한 for문을 사용하였을 때, 실행시간이 더 길어지는 것을 확인할 수 있다.

---

초기 틀린 이유

문제를 잘못 이해하고, 명령어가 "L"이나 "R"일 때, 잘못된 결과가 유도되도록 점화식을 짰다.

문제를 다시 꼼꼼히 읽고, 명령어가 "L"이나 "R"일 때의 점화식을 다시 만들어 문제를 해결할 수 있었다.

 

초기 점화식 (명령어가 "L"이나 "R"일 때)

digits == len(val) - 1과 의미하는 바가 같다.

# L 명령어
if val != 0:
    digits = int(math.log10(val)) 
    newVal = val // (10 ** digits) + (val % (10 ** digits) * 10)
else:
    newVal = 0

# R 명령어
if val != 0:
    digits = int(math.log10(val)) 
    newVal = 10 ** digits * (val % 10)  + val // 10
else:
    newVal = 0

명령어가 "L"일 때
13 -> 31
1234 -> 2341 

명령어가 "R"일 때
13 -> 31
1234 -> 4123

 

수정된 점화식 (명령어가 "L"이나 "R"일 때)

문제의 요구사항에 맞게 점화식을 수정하였다.

newVal = (val % 1000) * 10 + val // 1000 # L 명령어
newVal = (val % 10) * 1000 + val // 10 # R 명령어

명령어가 "L"일 때
13 -> 130 (0013 -> 0130)
1234 -> 2341 

명령어가 "R"일 때
13 -> 3001 (0013 -> 3001)
1234 -> 4123

 

 

정리

"n의 자릿수로 0 이 포함된 경우에 주의해야 한다."

위의 예시와 같이 a와 b가 각각 13, 31이라 생각해보자.

• 초기 점화식은 출력을 "L"이라 하는 반면, 수정된 옳은 점화식은 출력을 "DRDSLS"이라 한다.
• 즉, 레지스터에 저장된 n의 네 자릿수 중 0이 포함될 수 있으므로 이와 같은 경우를 유의해서 점화식을 짜야 한다.

---

💡 풀이 코드 (성공 - pypy3)

import sys
from collections import deque

def bfs(start, target):
    queue = deque()
    queue.append((start, ""))
    visited = set()
    visited.add(start)

    while queue:
        val, dslr = queue.popleft()

        if val == target:
            return dslr

        # D 명령어
        newVal = (2 * val) % 10000
        if newVal not in visited:
            visited.add(newVal)
            queue.append((newVal, dslr + "D"))

        # S 명령어
        newVal = val - 1 if val > 0 else 9999
        if newVal not in visited:
            visited.add(newVal)
            queue.append((newVal, dslr + "S"))

        # L 명령어
        newVal = (val % 1000) * 10 + val // 1000
        if newVal not in visited:
            visited.add(newVal)
            queue.append((newVal, dslr + "L"))

        # R 명령어
        newVal = (val % 10) * 1000 + val // 10
        if newVal not in visited:
            visited.add(newVal)
            queue.append((newVal, dslr + "R"))

t = int(sys.stdin.readline())
for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    result = bfs(a, b)
    print(result)

 

주요 로직

• A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 구하기 위해 BFS를 활용한다.
  • 이때, 같은 숫자에 대해 연산을 반복하는 것을 방지하기 위해 visited라는 set을 활용한다.
  • 즉, 각각의 D/S/L/R 연산을 수행한 새로운 값이 visited set에 없을 시에만 방문처리를 한 후 queue에 값을 삽입한다. 
  • queue에 값을 삽입할 때는 기존의 dslr 명령어에 이번에 수행된 D/S/L/R 연산에 대한 명령어를 추가해준다.

if newVal not in visited:
    visited.add(newVal)
    queue.append((newVal, dslr + "D"))

• L 명령어 수행
• R 명령어 수행

---

느낀점

1. 문자열 조작 연산은 비싸다. 따라서, 최대한 정수(모듈러 등) 연산을 활용하자.

2. 불필요한 for문은 성능 저하로 이어질 수 있다. 필요한 부분에만 사용하도록 하자.

3. 문제를 똑바로 읽자.