인프런 커뮤니티 질문&답변
작성한 질문수
4179 불! 3-D 질문합니다
작성
·
332
1
http://boj.kr/7504832be7504a4aafbf7fb84adc223d
왜 메모리 초과가 나는지 정말로 모르겠습니다.
강사님과 같이 배열 크기 1004 * 1004 사이즈 배열 3개 사용했구,
0 처리를 INF로 하는 부분 (불이 번지는 최단거리 배열에서) 빼면 솔직히 나 겁나 잘짠거 같다는 느낌마저 받았는데...ㅠ
답변 2
1
안녕하세요 go님ㅎㅎ
겁나는 아니고 한 어느정도는 잘 짜셨어요. ㅎㅎ
메모리 초과 등이 나면 이 코드의 불필요한 부분이 있나 확인하는게 중요한데요.
if (m[i][j] == 'F') f.push_back({ i,j });
- 이거 왜 visited 안 걸고 push_back 하시나요? + queue가 되어야 겠죠?
for (auto i : f)
BFS(i.first, i.second); // fire배열 만들기
- 왜 push_back 한 것을 활용하지 않고 또 갑자기 queue를 만드시나요? 애초에 fire queue를 만들고 그걸 기반으로 BFS 한번만 돌리면 되지 않을까요? 제가 처음에 여러개의 정점으로 부터 시작되는 BFS는 어떻게 하라고 말씀을 드렸죠? 해당 점을을 qeueue에 넣은 다음에 한꺼번에 돌리라고 했죠?
감사합니다.
0
음 좀 이해가 안되는 부분이 있는데요.
if ((nd <= fire[ny][nx] || fire[ny][nx] == 0) && (m[ny][nx] == '.' || m[ny][nx] == 'J')) {
이거 왜 이렇게 하시나요?
이렇게 하면 되는 거 아닌가요?
if(fire[ny][nx] || m[ny][nx] == '#')continue;
불이 0일 때(없을 때)는 사람이 움직일 때만 체크하면 되지 않을까요?
감사합니다.
답변 감사합니다.
http://boj.kr/5ab174c3fbb84c3980b2b70d0634f236
말씀하신대로 queue를 하나만 만들구 거기에 불의 좌표를 다 넣구 BFS를 한번만 돌리는 걸로 수정했고, 어차피 불의 최단거리 배열 만들고 나면 그 큐는 비어있을테니까 사람의 최단거리 배열을 만들때 똑같은 큐 사용했습니다만, 그래도 여전히 메모리 초과가 뜹니다..ㅠㅠ
INF로 처리하는 부분은
if ((vi[ny][nx] == 0)&&(m[ny][nx] == '.')&&( nd< fire[ny][nx] ||fire[ny][nx]==0)) { //초기값이 0이라서 0으로체크
이렇게 해서 불이 아직 번지지 않은 부분(fire[ny][nx]==0) 으로 고려 해줘서 테스트 케이스 만들어서 넣어보니 굴러갑니다.
http://boj.kr/5ab174c3fbb84c3980b2b70d0634f236