4-C 재귀 풀이 질문
http://boj.kr/089c2c9136d74ad080637a1d940ca88d
안녕하세요, 큰돌님.
비트마스킹이 익숙치 않아서, 우선 재귀로 풀어봤습니다.
풀다가 연결성 체크하는 부분에서 막혔는데, 어떤 방식으로 해야 될까요?
DFS로 할 수는 있을 것 같은데, 맞는 방향성이 아닌 것 같다는 생각이 듭니다...
답변 2
0
안녕하세요 ㅎㅎ
비트마스킹이 익숙치 않아서, 우선 재귀로 풀어봤습니다.
-> 그렇게 하셔도 됩니다.
다만,
일단 런타임 에러부터 해결해야 합니다.
vector<bool> A_t; // A: true, B: false
vector<vector<int>> v; // 연결된 구역을 담을 배열이부분에서 A_t 이거 처음에 크기를 10이상으로 주어야 합니다.
이부분을 일단 고쳐보시겠어요?
0
안녕하세요, 인프런 AI 인턴입니다. brigade98님.
재귀적으로 문제를 해결하시려는 시도는 매우 좋은 방향입니다. 재귀와 DFS(깊이 우선 탐색)는 그래프 탐색에서 가장 보편적인 방법 중 하나입니다. 연결성을 확인하는 데 DFS를 사용하는 것은 일반적인 접근 방식이므로 주저하지 마시고 시도해 보시기 바랍니다.
재귀와 DFS로 연결성 체크하는 방법:
기본 구조 설정: 그래프의 각 노드를 방문했는지 저장할 배열을 준비하세요. 이 배열은 이미 방문한 노드를 재방문하지 않기 위해 사용됩니다.
재귀 DFS 함수 작성:
- 현재 노드부터 시작하여 모든 인접 노드를 탐색합니다.
- 이미 방문한 노드를 다시 탐색하지 않도록 해야 합니다.
- 모든 노드를 탐색할 때까지 재귀적으로 탐색을 계속합니다.
- 현재 노드부터 시작하여 모든 인접 노드를 탐색합니다.
종료 조건 설정: 모든 연결성을 검사한 후, 탐색이 완료되었을 때 True나 False로 연결성을 판단할 수 있도록 조건을 명확히 설정합니다.
이전에 유사한 주제로 논의된 게시물을 참조하면 더욱 구체적인 솔루션을 발견할 수 있습니다. 예를 들어, 기존의 유사한 질문 및 답변을 확인하여 DFS를 통한 문제 해결 방법을 참고해 보세요.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
18
2
2주차 개념#12 트리 순회
0
20
2
백준사이트가 종료된다고 합니다.
0
234
2
백준 서비스 종료
9
742
1
sk 하이닉스 코테 대비
0
356
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
61
2
3-N 질문 있습니다.
0
66
2
학습방법
0
100
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
164
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
63
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
49
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
67
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
52
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
88
2
5-Q 질문
0
63
2
풀이 코드 질문
0
64
2