kinssang   2년 전

특별할게 없는 BFS를 사용한 풀이인데요

33% 쯤에 시간 초과도 아니고 메모리 초과가 떠버리니...


시간제한도 0.5초라 제대로 돌려도 시간초과가 뜰 것 같기도 한데


메모리 사용량 줄이는 방법은 어떻게 하는게 좋을까요?

제 체감상 크기가 큰 구조체가 큐에 들어가면서 메모리 사용량이 늘어나는게 문제인 것 같은데

remain, last 같은 애들은 구조체에 속해있지 않지만 remain_check를 통해 계산을 할 수 있긴 합니다.

int y, x도 하나짜리로 통합이 가능하긴 합니다.


어떻게 처리하면 메모리 초과를 피할 수 있을지 고수님들의 도움을 요청드립니다.


yukariko   2년 전

보통 bfs에서의 메모리초과는 중복처리에 문제가 있을 가능성이 많습니다.

위 코드에서는 visit에 대한 정보가 큐의 원소 각각에만 들어가 있고 통합되어있지 않아 중복된 원소가 들어가있을 확률이 높아보입니다.


그게 아니라 단순히 위 알고리즘 상에서 메모리를 줄이고 싶으시다면 remain check 배열과 visit 배열을 bitmasking 해준다면 메모리를 많이 줄일 수 있을것 같습니다.

kinssang   2년 전

visit에 대한 정보를 통합해서도 처리해봤는데

예시 인풋 같은 경우에 0->1->0->2 같은 경로들 때문에 0->1-> 돌아서 2로 가는 경로가 이미 visit되었다고 처리되어서  안되더라고요...

yukariko   2년 전

네 그래서 정점을 확장할필요가 있습니다. 예를들면 단순히 정점을 [y, x]로만 생각하는게 아니라 [지금까지 방문한모든장소, 현재 y,  현재 x] 같은 식으로요.

참고로 말씀드리자면 이 문제에선 0->2로의 방문은 불가능합니다.

yukariko   2년 전

정점의 확장을 이용한 bfs 문제의 예제로는

https://www.acmicpc.net/proble...

이 문제를 풀어보시면 도움이 될 것 같습니다.

kinssang   2년 전

아 예시 인풋인

##2##
#.0.#
3.#.#
##1##

에서 0에서 아래로 내려가서 1을 거친 후, 1에서 다시 0으로 간 후, 0에서 2로 가는 방문도 안되는 건가요?

이건 될 줄 알았습니다

yukariko   2년 전

아, 0에서 1을 이미 거쳤다면 0에서 2도 가능합니다.

제가 잘못 이해하고있었군요.

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