skyinyour   5년 전

백준 문제를 풀면서 틀리거나 시간초과는 많이 경험해봤지만 메모리초과는 경험이 별로 없어서 질문드립니다..

아래 코드처럼 항상 풀던 방식으로 BFS로 풀었는데 왜 메모리가 초과되는거죠.. ? 128MB나 주어지는데..;;

ryute   5년 전

BFS로는 Q에 들어가는 원소가 너무 많아질 수밖에 없습니다. 기왕 그래프로 모델링해서 해결하는 것이라면 조금 더 빠르게 최소한의 벽 부숨으로 목적지로 가는 방법을 구할 수 있는 방법을 찾는게 좋을 것 같습니다.

djm03178   5년 전

len + 1이 길이를 갱신할 때만 큐에 삽입해야 하는데, 같은 일이여도 큐에 삽입하기 때문에 중복 방문이 됩니다.

그리고 이 문제는 단순 BFS로 접근하면 틀립니다. 더 짧은 경로로 이동하는 것이 더 많은 벽을 부수는 것일 수도 있습니다. 문제 분류를 보세요.

skyinyour   5년 전

아하.. 다익스트라 분류인걸 봤지만 한번 호기로 BFS로 풀어보았습니다. 아무 생각없이 습관처럼 풀다보니 왜 큐에 너무 많은 원소가 들어가는지, 그리고 지금 제 코드에서 큐에 들어가는 원소의 갯수가 많은 편인지 조차 이해하기 힘드네요.. 감사합니다!

ckdgus2482   5년 전

현재 코드에서는 공간복잡도가 O(4^(n+m))입니다

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