-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
section7 송아지찾기 시간초과 질문드립니다.
21.01.21 23:27 작성 조회수 136
0
안녕하세요.
강의를 듣던 중에 질문이 있어서 글을 남기게 되었습니다.
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)
답변을 작성해보세요.
1
김태원
지식공유자2021.01.22
안녕하세요^^
visited[cur_location] = True
위에 줄에서 코드 오류입니다.
그리고 또 한가지 오류가 있습니다. 논리적으로 next_location이 좌표범위에 있는가 확인한 후 next_location의 방문여부를 체크해야 합니다. 5개 케이스에는 이 오류를 체크하는 입력이 없어서 통과되겠지만,
7000 3 을 입력하면 위 코드는 IndexError: list index out of range 에러가 발생합니다.
0
답변 2