후 이거보고 풀기 시작하다가 같은 문제로 탈탈 털리고 있다가 원인을 찾았어요.
큐에
(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 7년 전 1
고수님들 도와주세요. 처음 시도를 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로 바꿔 제출하니 맞았습니다.)