4-C 재귀 풀이 질문

작성한 질문수 7

0

안녕하세요 ㅎㅎ

비트마스킹이 익숙치 않아서, 우선 재귀로 풀어봤습니다.

-> 그렇게 하셔도 됩니다.

다만,

일단 런타임 에러부터 해결해야 합니다.

vector<bool> A_t; // A: true, B: false
vector<vector<int>> v; // 연결된 구역을 담을 배열

이부분에서 A_t 이거 처음에 크기를 10이상으로 주어야 합니다.

이부분을 일단 고쳐보시겠어요?

0

안녕하세요, 인프런 AI 인턴입니다. brigade98님.

재귀적으로 문제를 해결하시려는 시도는 매우 좋은 방향입니다. 재귀와 DFS(깊이 우선 탐색)는 그래프 탐색에서 가장 보편적인 방법 중 하나입니다. 연결성을 확인하는 데 DFS를 사용하는 것은 일반적인 접근 방식이므로 주저하지 마시고 시도해 보시기 바랍니다.

재귀와 DFS로 연결성 체크하는 방법:

1. 기본 구조 설정: 그래프의 각 노드를 방문했는지 저장할 배열을 준비하세요. 이 배열은 이미 방문한 노드를 재방문하지 않기 위해 사용됩니다.

2. 재귀 DFS 함수 작성:

   • 현재 노드부터 시작하여 모든 인접 노드를 탐색합니다.
     
   • 이미 방문한 노드를 다시 탐색하지 않도록 해야 합니다.
     
   • 모든 노드를 탐색할 때까지 재귀적으로 탐색을 계속합니다.
     

3. 종료 조건 설정: 모든 연결성을 검사한 후, 탐색이 완료되었을 때 True나 False로 연결성을 판단할 수 있도록 조건을 명확히 설정합니다.

이전에 유사한 주제로 논의된 게시물을 참조하면 더욱 구체적인 솔루션을 발견할 수 있습니다. 예를 들어, 기존의 유사한 질문 및 답변을 확인하여 DFS를 통한 문제 해결 방법을 참고해 보세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.