nh0903   2년 전

bfs의 시간복잡도가 node의 개수와 edge의 개수를 더한 O(V+E)인데 그럼 이 문제에서는 node는 좌표이고 edge는 하나의

좌표당 8개 이니깐 300*300*8 = 720,000 정도의 연산을 수행한다고 생각하는데 맞는건가요?

python3으로 코드를 실행하니깐 시간제한이 1초인데도 불구하고 시간초과가 뜨네요.(아래 코드는 while문에 break를

걸어줘서 정답처리 됩니다.) pypy3 역시 정답처리 됩니다.

제가 생각한 연산의 크기가 맞는건가요??

djm03178   2년 전

테스트 케이스의 수가 좀 많아서 그렇습니다. 한 파일에 여러 개의 테스트 케이스가 있는 문제이므로 그 모든 케이스를 전부 합쳐서 1초 안에 실행해야 하기 때문에 72만보다 훨씬 많은 연산을 수행해야 합니다.

Python 3는 보신 바와 같이 많이 느리기 때문에 앞으로도 항상 PyPy3만을 쓰시는 걸 권장합니다.

댓글을 작성하려면 로그인해야 합니다.