9466번 - 텀 프로젝트
최악의 경우의 수가 딱 저정도에 위치해있는 것 같습니다.
여기서 틀리시는 분들은, dfs 도중 싸이클이 발견되었어도, 시작점이 잘못되었기 때문에 다시 탐색을 돌아버리셔서 그럴 겁니다.
시작점이 어떻건 간에, dfs 도중 싸이클이 발견된다면... 해당 부분만은 사이클로 취급해서 불필요한 dfs를 줄여야합니다.
이렇게 안하시면 최악의 경우에는 사이클이 가장 마지막에 나오기 때문에, n^2가 됩니다.
댓글을 작성하려면 로그인해야 합니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
한국어 | English (Beta)
AltStyle によって変換されたページ (->オリジナル) / アドレス: モード: デフォルト 音声ブラウザ ルビ付き 配色反転 文字拡大 モバイル
expelia81 1년 전 8
최악의 경우의 수가 딱 저정도에 위치해있는 것 같습니다.
여기서 틀리시는 분들은, dfs 도중 싸이클이 발견되었어도, 시작점이 잘못되었기 때문에 다시 탐색을 돌아버리셔서 그럴 겁니다.
시작점이 어떻건 간에, dfs 도중 싸이클이 발견된다면... 해당 부분만은 사이클로 취급해서 불필요한 dfs를 줄여야합니다.
이렇게 안하시면 최악의 경우에는 사이클이 가장 마지막에 나오기 때문에, n^2가 됩니다.