4-C 재귀 풀이 질문2

작성한 질문수 7

0

안녕하세요 ㅎㅎ

연결성 체크하는 부분은 어떤 방식으로 구현해야 될까요?

-> DFS도 되고 BFS도 됩니다.

제가 한번 다듬어봤는데요. (불필요한 변수 제거 등) 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;

const int _MAX = 987654321;
int n, k, _k, res = _MAX;
int a[14];
vector<bool> A_t;
vector<vector<int>> v;

bool check(vector<int> group) {
    if (group.empty()) return false;
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(group[0]);
    visited[group[0]] = true;
    int cnt = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int next : v[cur]) {
            next--;
            if (!visited[next] && find(group.begin(), group.end(), next) != group.end()) {
                visited[next] = true;
                q.push(next);
                cnt++;
            }
        }
    }
    return cnt == group.size();
}

void go(int here) {
    if (here == n) {
        vector<int> A, B;
        for (int i = 0; i < n; i++) {
            if (A_t[i]) A.push_back(i);
            else B.push_back(i);
        }
        if (A.empty() || B.empty()) return;
        if (!check(A) || !check(B)) return;
        int sumA = 0, sumB = 0;
        for (int i : A) sumA += a[i];
        for (int i : B) sumB += a[i];
        res = min(res, abs(sumA - sumB));
        return;
    }
    A_t[here] = true;
    go(here + 1);
    A_t[here] = false;
    go(here + 1);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> _k;
            v[i].push_back(_k);
        }
    }
    A_t.resize(n);
    go(0);
    if (res == _MAX) cout << -1 << '\n';
    else cout << res << '\n';
    return 0;
}

0

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

말씀해주신 문제를 해결하면서 벡터의 크기를 지정하여 런타임 에러를 해결하신 점, 매우 잘하셨습니다. 연결성을 체크하는 부분에서 DFS(깊이 우선 탐색)를 사용하는 것은 흔한 방법입니다. DFS를 통해 그래프 탐색을 수행하여 서로 연결된 노드들을 효과적으로 검사할 수 있습니다. 연결성 체크를 위한 간단한 방법은 다음과 같습니다:

DFS를 활용한 연결성 체크 방법:

1. 방문 여부 확인 배열 준비: 그래프에 있는 각 노드를 방문했는지 확인할 배열을 준비하세요. 이는 중복 방문을 방지하기 위함입니다.

2. DFS 탐색 구현:

   • 시작 노드에서부터 연결된 모든 인접 노드를 탐색합니다.
     
   • 이미 방문한 노드는 무시하고, 방문하지 않은 노드는 재귀적으로 탐색을 계속합니다.
     

3. 그래프 전체 탐색: 모든 노드에 대해 DFS를 시도하여, 연결된 모든 그룹을 확인합니다.

예시 코드 (C++):

#include <vector>
#include <iostream>

std::vector<bool> visited;
std::vector<std::vector<int>> graph;

void dfs(int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

int main() {
    int numberOfNodes = ...; // 노드의 수
    graph.resize(numberOfNodes);
    visited.resize(numberOfNodes, false);

    // 그래프 초기화 코드 (간선 추가)

    for (int i = 0; i < numberOfNodes; ++i) {
        if (!visited[i]) {
            dfs(i);
            // 연결된 새로운 컴포넌트 발견 시 필요한 작업 수행
        }
    }
    return 0;
}

이 방법을 활용하면 DFS를 통해 연결된 노드들의 그룹을 모두 식별할 수 있습니다. 이 구조를 따라가면서 중복 방문을 피할 수 있고, 각 연결 컴포넌트가 탐색됨을 보장할 수 있습니다.

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

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