이 코드는 BFS가 아니라 DFS를 수행하고 있습니다. DFS로는 시간 초과를 피할 수 없습니다.
2178번 - 미로 탐색
DFS와 같이 완전 탐색을 하는 기법의 경우 일반적으로 지수 시간 복잡도가 걸립니다. 지수 복잡도라는 것은 일반적으로 어마어마하게 큰 복잡도이므로, 입력이 매우 작은 경우가 아니면 사용할 수 없다고 보시면 됩니다.
예를 들어, 매 칸마다 방문할 수 있는 다음 상태가 2개씩만 되더라도, 그 깊이가 100회만 될 수 있더라도 2^100이라는 수가 나오고 이 수는 연산이 아무리 빠르더라도 우주가 멸망할 때까지 다 계산을 할 수 없을 정도로 큰 수입니다. 칸이 100*100칸이라면 2^10000이 될 것이고, 이는 더더욱 절대 가능할 수가 없는 수치가 됩니다.
시간 복잡도의 개념에 대해 공부해 보시고, n, nlogn, n^2, 2^n, 3^n 등이 얼마나 빠르게 커지는 수인지 직접 계산해서 비교해보시면 그 차이를 느끼실 수 있을 것입니다. 일반적으로 컴퓨터는 1초에 10억 회 정도의 연산을 할 수 있는 것으로 보고, 시간 제한과 시간 복잡도에서 계산된 수가 어느 정도인지 대략적인 비교를 통해 코드가 얼마나 많은 시간이 걸릴지 대략적으로 예측할 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
jhs061116 3년 전 1
이 bfs의 시간 초과로 지적하실 부분이 있나요?ㅠㅠ
왜 틀렸는지 모르겠어요ㅠㅠ