아아앍ㄺ 파이썬 시간초과 ㅠㅠ (골드 4)

#9019번 DSLR https://www.acmicpc.net/problem/9019

9019번: DSLR

최소 연산 횟수 (최단거리 등) 은 무조건 BFS!

바로 짰다!

 

시간초과 코드

def cal_d(num):
    return num*2 % 10000


def cal_s(num):
    num -= 1
    if num <= 0:
        return 9999 + num
    else:
        return num


def cal_l(num):
    num = str(num)
    num = "0"*(4-len(num)) + num
    num = int(num[1:] + num[0])
    return num


def cal_r(num):
    num = str(num)
    num = "0"*(4-len(num)) + num
    num = int(num[3] + num[0:3])
    return num


def solve(prev_num, target_num):
    que.append([prev_num, ""])
    while que:
        prev, cmds = que.pop(0)
        if prev == target_num:
            return cmds

        for cal, cmd in [[cal_d, "D"], [cal_s, "S"], [cal_l, "L"], [cal_r, "R"]]:
            num = cal(prev)
            if not visited[num]:
                visited[num] = True
                que.append([num, cmds+cmd])
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    prev_num, target_num = map(int, input().split())
    visited = [False]*10000
    visited[prev_num] = True
    que = []
    print(solve(prev_num, target_num))

 

코드의 가독성을 높이고 싶어서, 함수들을 리스트 형태로 구성했다. 결과는 시간초과

함수로 구성한게 문제인가 싶어 단순하게 구성했다.

 

시간초과 코드2

def solve(prev_num, target_num):
    que = []
    que.append([prev_num, ""])
    while que:
        prev, cmds = que.pop(0)
        if prev == target_num:
            return cmds

        d_num = prev*2 % 10000
        if not visited[d_num]:
            visited[d_num] = True
            que.append([d_num, cmds+"D"])

        s_num = prev-1 if prev != 0 else 9999
        if not visited[s_num]:
            visited[s_num] = True
            que.append([s_num, cmds+"S"])

        l_num = int(prev % 1000*10 + prev/1000)
        if not visited[l_num]:
            visited[l_num] = True
            que.append([l_num, cmds+"L"])

        r_num = int(prev % 10*1000 + prev//10)
        if not visited[r_num]:
            visited[r_num] = True
            que.append([r_num, cmds+"R"])


for _ in range(int(input())):
    prev_num, target_num = map(int, input().split())
    visited = [False]*10000
    visited[prev_num] = True
    print(solve(prev_num, target_num))

문자열 연산이 시간을 많이 끌거라는 생각도 들어 연산 방법도 바꿨고, 함수 호출도 배제시켰다.

결과는 시간초과

 

아니 대체 왜...?

 

정답코드

def solve(prev_num, target_num):
    que = []
    que.append([prev_num, ""])
    while que:
        prev, cmds = que.pop(0)

        d_num = prev*2 % 10000
        if d_num == target_num:
            return cmds+"D"
        elif not visited[d_num]:
            visited[d_num] = True
            que.append([d_num, cmds+"D"])

        s_num = prev-1 if prev != 0 else 9999
        if s_num == target_num:
            return cmds+"S"
        elif not visited[s_num]:
            visited[s_num] = True
            que.append([s_num, cmds+"S"])

        l_num = int(prev % 1000*10 + prev/1000)
        if l_num == target_num:
            return cmds+"L"
        elif not visited[l_num]:
            visited[l_num] = True
            que.append([l_num, cmds+"L"])

        r_num = int(prev % 10*1000 + prev//10)
        if r_num == target_num:
            return cmds+"R"
        elif not visited[r_num]:
            visited[r_num] = True
            que.append([r_num, cmds+"R"])


for _ in range(int(input())):
    prev_num, target_num = map(int, input().split())
    visited = [False]*10000
    visited[prev_num] = True
    print(solve(prev_num, target_num))

연산을 했을 때 목표값에 도달하면 바로 정답을 return하는 형태로 변경했더니 시간초과가 나지 않았다.

그도 그럴 것이

1) D 연산 -> X라고 할 때

2) que 저장

 

위 과정을 S R L 모두 반복

 

이후

 

X 앞에 있는 모든 que 해결

 

1) X 호출

2) 정답여부 확인

 

이렇게 진행된다.

때문에 que에서 데이터를 pop하고 난 뒤 정답여부를 확인하는것 보단

연산을 하자마자 정답 여부를 확인하는게 시간을 더욱 단축시킨다고 할 수 있다.

 

BFS에서 꽤나 괜찮은 아이디어라는 생각이 든다.

 

https://www.acmicpc.net/board/view/76497

글 읽기 - 파이썬) 어디서 느려지는지 잘 모르겠습니다...

백준 질문에서는 문자열을 전달하는 행위 자체가 시간을 많이 소모한다고 한다.

때문에 visited 리스트에서 True 값을 저장하는게 아닌 이전 경로를 저장하는 형태로 진행하는게 더 빠를거라고 한다.

하지만... 이전 경로를 저장한 후 사용된 명령어를 다시 모아 출력하는걸 구현할 자신이 없었다.

 

누가 좀 알려줬으면 좋겠다 ㅠㅠ