Cộng đồng Hỏi & Đáp của Inflearn

skgudwn340926

câu hỏi đã được viết

Giới thiệu về giải bài toán bằng thuật toán Python (chuẩn bị cho bài kiểm tra viết mã)

section7 송아지찾기 시간초과 질문드립니다.

Viết

237

안녕하세요.

강의를 듣던 중에 질문이 있어서 글을 남기게 되었습니다.

section7 bfs문제인 송아지찾기, input 4,5 파일에서 시간초과가 나는데 이유를 알 수가 있을까요?

아래는 제가 짠 코드이며 알고리즘은 같지만 스타일만 조금 다릅니다.

답변 주시면 감사하겠습니다.

import sys
from collections import deque

# sys.stdin = open("input.txt","r")

def find_calf(location):

    queue = deque()

    queue.append(location)

    visited[location] = True
    
    while queue:

        ### 현재 현수의 위치
        cur_location = queue.popleft()

        if cur_location == E:
            break
        
        ### 현수는 +1, -1, +5 중 하나의 혀애로 이동
        for next_location in [cur_location+1, cur_location-1, cur_location+5]:
            
            ### 다음이동위치가 방문하지 않았을 때,
            if visited[next_location] == False:

                ### 좌표의 범위는 1~10000
                if next_location>=1 and next_location<=10000:

                    queue.append(next_location)

                    visited[cur_location] = True
                    count[next_location] = count[cur_location]+1

    print(count[cur_location])


if __name__ == '__main__':

    S, E = list(map(int, sys.stdin.readline().split()))
    
    ### 위치 방문여부를 체크
    visited = [False] * 10001

    ### 위치까지 가는 횟수를 저장
    count = [0] * 10001

   find_calf(S)