인프런 커뮤니티 질문&답변
작성한 질문수
3-D 맞왜틀팁 질문
해결된 질문
작성
·
23
0
안녕하세요 선생님!
저는 3-D (4179) 문제를 다른 방식으로 풀었어요.
불이 확산되는 속도 vs 사람이 빠져나가는 속도를 비교한게 아니라, 매 loop마다 불을 먼저 확산시키고, 그다음 사람을 움직여보면서 탈출 가능여부를 체크했어요.
또한, index를 0이 아닌 1부터 사용하도록 구현해두어 그에 맞게 조건문들도 구현해두었고요.
제가 만든 테스트 케이스, gpt가 만들어준 테스트 케이스는 전부 통과하는데 백준에서는 계속 틀렸다고 나오네요.
어떤 테스트 케이스에서 걸리는건지 도통 모르겠는데, 도와주실 수 있으신가요?
http://boj.kr/fafb46e051fc462fb1c2e8c1f12c403f
답변 2
0
안녕하세요 케이님 ㅎㅎ
visited를 사람과 불이 공유하면 사람 방문 -> visited -> 불이 해당 visited를 건너뛰게 되는 상황이 발생할 수 있을 것 같습니다.
나눠서 해보시겠어요?
감사합니다.
안녕하세요 ㅎㅎ
그 이유는 사람이 불의 확산을 막는 경우에는 이미 '사람이 먼저 해당 위치에 도달' 한 것이므로, 사람이 먼저 탈출할 수 있다고 판단했기 때문이에요.
->
듣고보니 케이님 말씀이 맞네요. ㅎㅎ 이부분은 제가 잘못 판단했네요..
맞습니다. visited는 하나로도 가능할 것 같습니다.
근데 그러면...
pair<int,int> here = humamQueue.front(); humamQueue.pop();
for(int i = 0; i < 4; i++){이부분은 고쳐야 합니다.
hsize = humamQueue.size() 이런식으로 해놓고 해당 사이즈만큼 루프를 돌아야 -> 불 -> 사람이 돌 수 있는 모든 경우의 수 -> 불 -> 사람... 이 로직이 이뤄지지 않을까요?
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다. K케이님!
3-D 문제(4179번)에서 불과 사람의 확산을 다루는 방식과 관련해서는 여러 차례 같은 문제를 경험한 다른 수강생들의 질문이 있었으며, 그에 대한 정보가 도움이 될 수 있습니다. 특히, 백준에서 계속 틀렸다고 나오는 문제의 원인을 찾기 위해서는 몇 가지 일반적인 함정을 고려해 볼 수 있습니다. 여기 몇 가지 참고할 만한 해결 방법들을 소개합니다:
범위 처리의 중요성:
- 인덱스를
1부터 시작하셨다고 하니, 각 인덱스의 범위가 적절하게 처리되고 있는지 확인해보시기 바랍니다. 특히, 배열의 크기를 초과하지 않도록 조심해야 합니다.
- 인덱스를
불과 사람의 이동 조건:
- 불이 퍼지고 사람의 이동 조건이 적절하게 설정되지 않은 경우가 많습니다. 예를 들어, 사람이 이동 가능한 위치와 불이 이미 도달한 위치가 충돌하는지, 사람들이 불이 있는 곳으로 이동하려고 시도하는지를 확인하세요.
- 불이 퍼지고 사람의 이동 조건이 적절하게 설정되지 않은 경우가 많습니다. 예를 들어, 사람이 이동 가능한 위치와 불이 이미 도달한 위치가 충돌하는지, 사람들이 불이 있는 곳으로 이동하려고 시도하는지를 확인하세요.
우선순위 및 처리 순서:
- 불을 확산시키고 나서 사람의 이동을 처리하는 것은 일반적인 방법이긴 합니다만, 이 방식이 모든 경우에 정확히 동작하는지 다시 검토해봐야 합니다. 특히, 경계 조건이나 모서리 조건에서 문제가 발생할 수 있습니다.
- 불을 확산시키고 나서 사람의 이동을 처리하는 것은 일반적인 방법이긴 합니다만, 이 방식이 모든 경우에 정확히 동작하는지 다시 검토해봐야 합니다. 특히, 경계 조건이나 모서리 조건에서 문제가 발생할 수 있습니다.
관련 질문 및 해결 방법을 소개합니다:
- 4179 불! 문제 질문
- #3-D 반례 질문
- 3-D 문제 질문있습니다
이 링크들에서는 다른 수강생들이 경험한 반례와 그에 대한 해결 방법이 다루어져 있습니다. 불과 사람 모두 BFS를 기반으로 처리하면서 조건들을 꼼꼼하게 확인하고, 각 처리 단계 후 적절하게 큐 및 방문 여부를 관리하는 것이 중요합니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
좋은 의견 감사합니다. 다만 선생님이 말씀해주신 상황이 발생하는 예시가 있을까요?
지금 제 코드는
불 확산(상,하,좌,우) -> 2. 사람 확산(단, 벽과 불을 피해서) -> 3.edge 도달 시 탈출
의 과정을 거치고 있어요. 따라서 불이 먼저 확산되므로, 불이 사람이 가는 길을 막았으면 막았지 사람이 불의 확산을 막는 경우는 고려하지 않아도 된다고 생각했어요.
그 이유는 사람이 불의 확산을 막는 경우에는 이미 '사람이 먼저 해당 위치에 도달' 한 것이므로, 사람이 먼저 탈출할 수 있다고 판단했기 때문이에요.
혹시 제 생각의 흐름에서 잘못된 부분이나, 고려하지 못한 부분이 있나요?
그리고 가능하다면 제 코드의 반례도 찾아보고 싶어요.