[백준] 9019번 DSLR (by Python)

문제

다른 것을 하다가 싫증이 나서 가볍게 머리도 풀 겸 고른 BFS 문제인데, 나에게 또다른 시련을 안겨줄 줄은 몰랐다. 논리적으로 풀기 어려운 문제는 아니었으나, 구현하는 내가 자잘한 실수를 발견하지 못한 탓에 성공까지 시간이 좀 걸렸다. PS는 논리력만큼이나 꼼꼼함도 중요하다는 것을 되새기게 된 문제이다.

 

풀이

from collections import deque
import sys

def check(x, char):
    global parents
    global q
    global b
    global a
    global temp
    if parents[x][0] == -1:
        parents[x][0] = temp
        parents[x][1] = char
        q.append(x)
    if b == x:
        answer = ''
        while b != a:
            answer = parents[b][1] + answer
            b = parents[b][0]
        print(answer)
        return True

    return False


input = sys.stdin.readline
t = int(input())

for _ in range(t):
    parents = [[-1, ''] for _ in range(10000)]
    a, b = map(int, input().split())
    q = deque()
    q.append(a)

    while q:
        temp = q.popleft()
        d = temp * 2 % 10000
        if check(d, 'D'):
            break
        s = 9999 if temp == 0 else temp - 1
        if check(s, 'S'):
            break
        l = (temp % 1000) * 10 + (temp // 1000)
        if check(l, 'L'):
            break
        r = (temp % 10) * 1000 + (temp // 10)
        if check(r, 'R'):
            break

 

주어진 조건대로 D, S, L, R의 연산을 구현하여 BFS를 실행하고 도달했을 때의 경로를 찾는 문제인데, 기본적인 BFS의 틀에서 크게 벗어나있지는 않아서 큰 고민을 하며 코드를 짜진 않았다. 그러나 두 가지를 간과한 탓에 여러 번의 시행착오를 겪게 되었다.

첫 번째는 명령어 나열을 거꾸로 출력한 것이다. parents 배열을 두고 최종 도착지에서 출발지까지의 경로를 역추적하는 방식이므로, 명령어의 나열을 출력하기 위해서는 순서를 반대로 뒤집어주는 것이 맞았다. 하지만 그런 생각을 미처 하지 못했고, 설상가상으로 테스트 케이스들도 거꾸로 해도 정답이 되는 것들이어서 (일부러 그렇게 만들었는지도?) 더 헤매게 되었다.

두 번째는 큐에서 나왔을 때 목표에 도달했는지 검사한다는 것이다. 이렇게 되면 그 이전에 같은 depth를 모두 거치게 되기 때문에 시간적으로 불리할 수밖에 없다. 가뜩이나 이 문제는 목표시간 안에 완료하는 것이 어려운 문제라서 더 그렇다. (정답자들을 확인 했을 때 Python 3 환경에서 통과하신 분은 한 분밖에 없었다... 리스펙 나는 Pypy3 환경에서 제출했다) 때문에 큐에 집어넣을 때에 검사를 하는 방식으로 바꾸어주었고, 다행히도 성공할 수 있었다.

에러가 나도 침착하게 디버거의 마음으로 한줄한줄 내가 생각한 대로 돌아가고 있는지 짚어볼 것.