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

kundol · Answer

안녕하세요 ㅎㅎ 담부터는 들여쓰기 부탁드립니다 ㅎㅎ 일단 답변 드리면요. 실제로 "시간이 1초 흐르면 불이 퍼지고, 그 다음 사람이 움직인다"를 그대로 시뮬레이션하려고 하셨습니다. 다만 이 방식은 매 순간마다 불의 상태와 사람의 상태를 함께 관리해야 해서 경우의 수가 급격히 증가합니다. 여기서 먼저 최단시간 & 가중치가 같은 그래프라면 -> BFS를 생각해야 합니다. 더나아가 움직이는 주체가 여러 개인가? 서로 영향을 주는가? 그렇다면 각각의 "최단 도착 시간"을 따로 구할 수 없는가? 를 생각하는 것이죠. 이문제는 각각의 최단시간이기 때문에 불도 BFS 사람도 BFS 가 가능해집니다. 여기서 불도 결국 모든 칸으로 퍼져나가는 최단거리 문제이고, 사람도 결국 모든 칸으로 이동하는 최단거리 문제입니다. 라고 확장하는 것이죠. 자 이제 2단계. 그러면 "사람이 (y,x)에 5초에 도착" "불이 (y,x)에 3초에 도착" 이라는 정보가 생기고, 5 >= 3 이므로 못 간다 라는 판단을 매우 쉽게 할 수 있습니다. 팁으로 : 퍼진다. 탐색한다. 라고 워딩이 나오면 DFS를 생각하기 마련인데 최단거리 & 같은 가중치라는 문제인경우 -> BFS를 생각해야 합니다. 코드리뷰는 다음과 같습니다. fires.pop_back(); 이런식으로 불을 원복하셨고 현재 사람이 선택한 경로에 맞춰 불도 같이 진행했다가 되돌리는 로직인데 불은 사람의 행동과 무관하게 퍼지게 됩니다. 사람의 모든 경로를 DFS로 탐색 각 경로마다 불을 퍼뜨림 되돌아오면서 불 상태도 복구 이 3가지가 비효율적이기도 하구요. ㅎㅎ 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.

communityai8509 · Answer

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