scka   2달 전

처음에 m.insert(make_pair(next,1));

했을때 매모리 초과가 났습니다.

그런데 코드를 m[next] = 1;  로 바꾸니까 통과했습니다.

map에서 insert 하는 것이 시간초과면 몰라도 메모리 초과가 나는 이유는 

모르겠어서 질문 드립니다.

yukariko   2달 전

map에서는 중복된 key를 갖는 요소를 만들 수 없습니다.

즉, map[next] 가 0으로 들어있는 시점에서 map.insert(next, 1)을 해도 map[next]는 변함없이 0인거죠.

따라서 bfs가 중복체크를 하지 못하게되고 큐가 계속 쌓여서 메모리초과가 발생하게 됩니다.

결론은 map[next] = 1과 같이 삽입이 아니라 수정을 통해서 수행해야 합니다.

map.insert를 사용하고 싶다면, if문을 다음과 같이 바꾸면 됩니다.

if(m.find(next) == m.end())


scka   2달 전

아! 그런거군요!

덕분에 잘 이해했습니다.

감사합니다~


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