mhccc   2년 전

우선 정답을 받아내긴 했는데 실행 시간이 오래걸려서 좋은 답은 아닌 것 같아 질문 올립니다.

제 코드에서 어떤 부분이 시간을 많이 잡아먹고 있는 것인가요?? 도움 부탁드립니다. 감사합니다 (_ _)

djm03178   2년 전

BFS로 한 단계 나아갈 때마다 기존의 path를 받아서 이어붙이면 그 길이에 비례하는 시간이 매번 걸려서 비효율적입니다. string을 만들고 지우는 것 자체가 꽤 무거운 연산이기도 합니다.

BFS의 경로를 추적할 때 완성품을 보내주지 말고, 이전 상태가 어디였고 거기서 무슨 연산을 한 건지만 알려주면 BFS가 끝난 후에 경로를 역추적해서 재구성을 할 수 있습니다. string 대신에 char을 쓸 수 있어서 더 가볍습니다.

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