4179 불! 3-D 질문합니다
390
작성한 질문수 9
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
답변 감사합니다.
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
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일 때(없을 때)는 사람이 움직일 때만 체크하면 되지 않을까요?
감사합니다.
1-E질문입니다!
0
520
2
3-L 틀린 부분 피드백 부탁드립니다.
0
825
2
1-A문제 순열재귀함수 질문입니다.
0
389
1
1-A 일곱난쟁이문제입니다
0
459
1
문제 풀 때 방향성에 대해
0
803
1
맥에서 vs code로 실행 관련 질문입니다
0
524
1
17071번 메모리 초과
0
387
1
1-C질문입니다!
0
424
2
2-B BFS 시간초과질문
0
632
2
1-O 13번 라인
0
443
1
6-J 놀이공원 문제 질문
0
383
1
구현관련 질문
0
485
1
강의 교안
0
321
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
547
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
536
1
1-K
0
475
2
3-G번 질문있습니다.
1
476
3
3-C 실행 시간 질문드립니다.
0
495
1
4-A 문제 풀이 질문있습니다.
0
591
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
435
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
336
1
3-O go 함수 질문 드립니다.
1
449
2
4-A 출력 질문
0
305
1
1주차 1-O 질문드립니다
0
260
1