Inflearn Community Q&A

안녕하세요 ㅎㅎ

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

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

다만,

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

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

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

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

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

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

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

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

2. 재귀 DFS 함수 작성:

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

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

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

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