인프런 커뮤니티 질문&답변

HyeongJu Na

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

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

작성

226

안녕하세요.

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

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)