5014 스타트링크 백준 파이썬

피드백)

계속 시간초과가 났다 분명 맞게 한 것 같은데... 왜 자꾸 시간초과가 나는지...

입력이 백만이라 그런걸까 계속 생각해봤지만 답이 나오지 않아 질문하기란을 살펴보던 도중

나랑 같은 케이스인 분이 계셨다 답글을 읽어보니

visited의 위치가 문제였다.

꺼내면서 visited를 갱신하면 큐에 중복되는 층 들이 계속 쌓여서 큐의 길이가 무지막지하게 커지는 것이다.

그래서 시간초과가 나온 것이다...

앞으론 꺼낼때 visited를 갱신하지 말고 큐에 넣으면서  동시에 visited를 갱신하는 식으로 해야겠다.

오랜만에 해서 감이 떨어졌나보다 ㅋㅋ;

 

소스코드)

from collections import deque
totalFloor, ghcurrent, startlinkf, up, down = map(int, input().split())

visited = [0 for _ in range(totalFloor+1)]
q = deque()
cnt = 0
q.append((ghcurrent, cnt))
visited[ghcurrent] = 1

while q:
    cur, cur_cnt = q.popleft()
    if cur == startlinkf:
        print(cur_cnt)
        exit()

    upnx = cur + up
    downnx = cur - down

    if 1 <= upnx <= totalFloor:
        if not visited[upnx]:
            q.append((upnx, cur_cnt+1))
            visited[upnx] = 1
    if 1 <= downnx <= totalFloor:
        if not visited[downnx]:
            q.append((downnx, cur_cnt+1))
            visited[downnx] = 1
if len(q) == 0:
    print("use the stairs")