wjddms206   4년 전

고수님들 도와주세요. 처음 시도를 BFS로 했습니다. 그러나 메모리 초과가 났습니다.

제 코드는 아래와 같습니다. 

그런데 이해가 안가서 질문드립니다. 이 문제의 메모리제한은 128MB입니다.

제가 사용한 int arr[100][100], int visit[100][100], int dy[4], int dx[4], int n 이렇게 합쳐서 

100*100*2*4byte(arr, visit배열) + 4*2*4byte(dy,dx 배열) + 4byte(전역변수 n) = 80,036 byte (즉, 대략 80KB) 라고 생각했습니다.

그리고 queue는 void bfs(int, int, int) 함수 안에 있어서 함수 호출이 끝나면 메모리 자동 해제 될거라고 생각했습니다.

제가 잘못 생각 한 것인가요? 너무나 궁금합니다.. 고수님들 도와주세요ㅠ_ㅠ 저의 생각을 고쳐주세요 부탁드립니다.

(참고로 DFS로 바꿔 제출하니 맞았습니다.)

luluctrl4   4년 전

후 이거보고 풀기 시작하다가 같은 문제로 탈탈 털리고 있다가 원인을 찾았어요.

큐에

(2, 1), (1,2), (2, 3) 있어요

그 다음 얘네들이 갈 곳이 (2, 2) 밖에 없을때
한 번 방문해서 닫아줘야하는데 그걸 (2, 2)가 큐에서 꺼내질때 닫아지니
저거 3개 모두다 (2, 2)를 한번씩 추가해서 3개가 중복되어 들어가 있어요

이후 (2, 2)에서 다음 갈곳이 (3, 2) 라고 하면
(3, 2) 닫는 것도 (3, 2)가 큐에서 꺼내질 때 닫으니까
(2, 2)가 3번 호출한 만큼 (3, 2) 3번 큐에 쌓임

그러니 맨처음 (while 이전)과 push할 때마다 닫아주면 메모리 초과 안 나요

wjddms206   4년 전

진짜... 너무너무너무 감사드려요 !!!! 

무슨말인지 이해 쏙쏙 잘 되고, 어디에서 실수했는지 저를 돌아보는 계기가 되었습니다.

BFS로 다시 제출해서 AC 받았습니다.

너무나 감사합니다. 좋은 하루 되세요!!!!

skynet   3년 전

간사합니다!

jongyeon95   1년 전

감사합니다 잘 참고하고 갑니다!!

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