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

안녕하세요 ㅎㅎ

Q. 해설에 노드는 25개라고 하셨는데,

워스트 25 * 25해서 625개가 아닌가요?

-> 네 맞습니다. 이게 보통은 400개 이하여야 가능합니다만 이 문제의 시간초과가 2초이고 +225개라서 되는 것 같습니다. 개념교안내에도 이부분은 보안설명해놓겠습니다.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. mhyim님.

플로이드 워셜 알고리즘과 다익스트라 알고리즘의 차이를 고려하여 적절한 알고리즘을 선택하는 과정에서 헷갈리셨군요. 해설에서 다루어진 ‘노드 25개’라는 부분에 대해 설명드리겠습니다. 일반적으로 플로이드 워셜 알고리즘은 모든 노드 쌍 간의 최단 거리를 구하기 때문에, 노드의 수가 많아질수록 시간복잡도가 급격히 증가합니다. 플로이드 워셜의 복잡도는 (O(N^3))이고, 보통 노드 수가 400 이하일 때 적절히 동작할 수 있는 수준입니다.

이 문제는 노드 수가 25개 정도로 제한되어 있어, 이론상 플로이드 워셜을 사용할 수 있는 상황입니다. 하지만 필요에 따라 특정 문제는 더 효율적인 방법이 있을 수 있습니다. 다익스트라 알고리즘은 특정 노드에서의 최단 경로를 구하면서 효율적인 계산을 할 수 있으므로, 문제의 조건을 고려하여 알맞게 선택하시면 됩니다.

플로이드 워셜을 사용하지 않으신 이유는 이해할 수 있습니다. 다만, 문제 요구 사항에 따라 어느 알고리즘이 더욱 합리적인 선택인지 고민하는 과정은 유익합니다.

아래 링크를 통해 플로이드 워셜과 다익스트라에 관한 추가 설명을 확인해 보시면 도움이 될 수 있습니다.

• 플로이드 워셜 알고리즘 개요 및 사용법
  
• 다익스트라 알고리즘 개요 및 사용법
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.