3-D 관련 질문

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 강사님, 저는 이 문제를 풀며 불의 최소 거리와 사람의 최소 거리를 비교하며 풀 생각을 못했고, 그래서 DFS를 사용하면서, 불을 먼저 이동시키고 사람을 이동시키면서 불을 만나지 않고 탈출하는 경우에 대해 값을 찾았었습니다. #include using namespace std; int N,M; int dy[4] = {0,0,1,-1}; int dx[4] = {1,-1,0,0}; int min_exit = INT_MAX; vector> inp_map; vector> fires_map; vector>> fires; vector> visited; bool can_exit = false; void fire_flood(int level) { for (int f=0; f= 0 && nx >= 0 && ny < N && nx < M && inp_map[ny][nx] != 0 && inp_map[ny][nx] != 2) { fires_map[ny][nx] = 1; fires[level+1].push_back(make_pair(ny,nx)); } } } } void return_flood(int level) { for (int f=0; f>()); fire_flood(level); for (int i=0; i<4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny >= 0 && nx >= 0 && ny < N && nx < M && inp_map[ny][nx] != 0) { if (inp_map[ny][nx] == 1 && visited[ny][nx] == 0) { dfs(ny, nx, level+1); } } } return_flood(level+1); fires.pop_back(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); fires.push_back(vector>()); cin >> N; cin >> M; int sty, stx; for (int i=0; i()); fires_map.push_back(vector(M,0)); visited.push_back(vector(M,0)); string temp; cin >> temp; for (int j=0; j

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. pshpark12345님, 질문에 대한 답변을 드립니다. 귀하의 문제는 불길과 사람이 동시에 움직이는 환경에서 최단 경로를 찾아 탈출해야 하는 과제입니다. 이 문제의 핵심은 즉, 불과 사람의 이동을 서로 독립적으로 BFS로 계산 하여, 불이 도달하기 전에 사람이 탈출할 수 있는지를 판단하는 것입니다. 코드 개선 및 로직 설명 귀하의 코드는 DFS를 사용하여 불을 퍼뜨린 뒤, 사람을 이동시켜 문제를 해결하려 했습니다. 하지만, 이 방식은 폭발적으로 증가하는 상태 공간에서 효율적이지 않을 수 있습니다. BFS를 사용하여 불이 퍼지는 시간을 먼저 계산하고, 그 뒤에 사람이 이동 가능한 경로를 탐색하는 방식이 더 효과적입니다. 불의 퍼짐 BFS : fire_bfs 함수는 불이 각 위치에 도달하는 시간을 기록합니다. 각 단계에서 불이 주변으로 퍼져 나가며, 이 시간을 기록합니다. 지훈이의 탈출 BFS : jihoon_bfs 함수는 지훈이가 각 위치에 도달하는 시간을 기록하면서, 불보다 먼저 특정 경계에 도달하는지를 확인합니다. 학습 및 사고의 확장 불과 사람의 이동을 각각 BFS로 구현하는 이유는, 불이 어디까지 퍼질지와 사람이 어디로 갈 수 있는지를 독립적으로 파악하기 위함입니다. 이러한 생각을 키우려면 다음과 같은 연습을 해보세요: 유사 문제를 많이 풀기 : 다양한 경로 탐색 문제를 풀면서, BFS와 DFS의 차이점 및 적절한 사용처를 익히는 것이 중요합니다. 구체적 문제 분석 : 문제를 여러 관점에서 분석해보고, 상태를 나누어 생각하면서 가장 효율적인 방법을 찾아보세요. 기존 해답 연구 : 다른 사람의 풀이를 보고, 그들의 사고방식을 이해하려 노력하세요. 이는 본인만의 전략을 세우는 데 큰 도움이 됩니다. 관련된 추가 상세한 설명이나 유사한 문제에 대한 조언과 생각도 다른 게시물에서 찾아보실 수 있습니다. 3-D 문제 시간초과 해결 방법 도 같은 문제를 해결하는 데 도움이 될 수 있습니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.