jangtai4   1년 전

BFS로 풀었습니다 제한시간 6초는 통과하였지만 제출하신 분들 내용을 보고 50ms 걸린 거 보고 좀 충격 먹었습니다.

제가 아직 초보라 현재 사용한 BFS 알고리즘에서 시간을 줄일 수 있는 방법을 알려주신다면 정말 감사드리겠습니다.

위 경우가 아니더라도 N log N으로 떨어트리려면 어떤 사고방식이나 알고리즘이 필요한가요?

corhydrae   1년 전

알고리즘을 개선하고 싶으시다면 bidirectional BFS 쓰시면 될 겁니다.

A/B에서 각각 정방향/역방향으로 번갈아가며 탐색하다가 마주치는 지점에서 멈추면 됩니다.

jangtai4   1년 전

알겠습니다. 감사합니다!!!!!

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