이 코드는 BFS가 아니라 DFS를 수행하고 있습니다. DFS로는 시간 초과를 피할 수 없습니다.

아 bfs라고 잘못 말해버렸네요 ㅠㅠ

이문제는 방법이 bfs밖에 없나요 ㅠㅠ

최단 거리 문제는 DFS로 할 수 없습니다. 각 칸에 처음으로 도달한 순간이 가장 빠르게 도달한 경로라는 보장이 없기 때문에 매번 재방문을 해야 하는데, 이것이 반복되면 시간 복잡도가 지수 형태가 되어 너무 오래 걸리게 됩니다.

djm03178

항상 코린이들에게 답변 해주셔서 감사합니다.

궁금한 게 있어서 글 남깁니다.

저는 dfs를 사용하여 모든 경로로 방문 했을 때의 거리를 저장하고 최솟값을 출력했습니다.

하지만 말씀하신 대로 시간초과가 나왔는데, n,m의 범위가 1~100 사이라서 괜찮을 거라고 생각했습니다.

혹시 시간초과를 예상하는 방법이 있을까요?

DFS와 같이 완전 탐색을 하는 기법의 경우 일반적으로 지수 시간 복잡도가 걸립니다. 지수 복잡도라는 것은 일반적으로 어마어마하게 큰 복잡도이므로, 입력이 매우 작은 경우가 아니면 사용할 수 없다고 보시면 됩니다.

예를 들어, 매 칸마다 방문할 수 있는 다음 상태가 2개씩만 되더라도, 그 깊이가 100회만 될 수 있더라도 2^100이라는 수가 나오고 이 수는 연산이 아무리 빠르더라도 우주가 멸망할 때까지 다 계산을 할 수 없을 정도로 큰 수입니다. 칸이 100*100칸이라면 2^10000이 될 것이고, 이는 더더욱 절대 가능할 수가 없는 수치가 됩니다.

시간 복잡도의 개념에 대해 공부해 보시고, n, nlogn, n^2, 2^n, 3^n 등이 얼마나 빠르게 커지는 수인지 직접 계산해서 비교해보시면 그 차이를 느끼실 수 있을 것입니다. 일반적으로 컴퓨터는 1초에 10억 회 정도의 연산을 할 수 있는 것으로 보고, 시간 제한과 시간 복잡도에서 계산된 수가 어느 정도인지 대략적인 비교를 통해 코드가 얼마나 많은 시간이 걸릴지 대략적으로 예측할 수 있습니다.