인프런 커뮤니티 질문&답변

안녕하세요 인성님 ㅎㅎ

void 도 괜찮습니다. 다만 dfs 부분을 다음과 같이 수정해주셔야 합니다.

void dfs(int here, const vector<int>& area) {
    visited[here] = 1;
    for (int next : adj[here]) {
        if (!visited[next] && find(area.begin(), area.end(), next) != area.end()) {
            dfs(next, area);
        }
    }
}

제가 좀 다듬은 전체코드는 다음과 같습니다.

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

int n;
int a[14];
vector<int> adj[14];
int visited[14];
const int mx = 987654321;
int ret = mx;

void dfs(int here, const vector<int>& area) {
    visited[here] = 1;
    for (int next : adj[here]) {
        if (!visited[next] && find(area.begin(), area.end(), next) != area.end()) {
            dfs(next, area);
        }
    }
}

bool check(const vector<int>& area) {
    for (int i : area) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

int cnt(vector<int> v1, vector<int> v2) {
    int x1 = 0;
    int x2 = 0;
    
    for(int i : v1) {
        x1 += a[i];
    }
    for(int i : v2) {
        x2 += a[i];
    }
    
    return abs(x1 - x2);
}


int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < x; j++) {
            int temp;
            cin >> temp;
            adj[i].push_back(temp);
            adj[temp].push_back(i);
        }
    }

    for (int i = 1; i < (1 << n) - 1; i++) {
        vector<int> area1, area2;

        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                area1.push_back(j + 1);
            } else {
                area2.push_back(j + 1);
            }
        }

        fill(&visited[0], &visited[0] + 14, 0); 
        dfs(area1[0], area1);
        bool temp1 = check(area1); 
        fill(&visited[0], &visited[0] + 14, 0); 
        dfs(area2[0], area2);
        bool temp2 = check(area2);

        if (temp1 && temp2) {
            ret = min(ret, cnt(area1, area2));
        }
    }

    if (ret == mx) {
        cout << -1 << "\n";
    } else {
        cout << ret << "\n";
    }
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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

황인성 님의 질문에 대해 유사한 기존 질문과 답변을 검색하여 관련 정보를 제공해 드리겠습니다.

DFS와 BFS는 서로 다른 탐색 기술로, 문제 상황에 따라 적절히 선택하여 사용해야 합니다. DFS를 힙 기반 구조(예: 재귀 호출)를 사용하여 구현할 때 메모리나 시간 초과 오류가 발생할 수 있습니다. 특히, 깊이가 깊거나, 재귀 호출에 의존해야 하는 상황에서 문제가 발생할 확률이 높아집니다.

해당 문제에 대한 유사한 질문으로, 4-H 질문있습니다의 답변을 참고하시면 도움이 될 것입니다. 이 게시물에서는 DFS를 구현할 때의 주의점과 여러 가지 해결 방법에 대해 설명되어 있습니다. 주로 함수 호출 순서와 코드 로직에 따라 발생할 수 있는 문제를 어떻게 해결할 수 있을지에 대한 팁을 제공합니다.

특히, void 형 DFS를 사용하는 경우 함수가 끝난 후 상태를 원복하지 않아 생길 수 있는 상태 유지 문제를 간과할 수 있으므로, call stack의 끝에서 다시 시작하는 상태 관리를 주의깊게 보셔야 합니다. 또한, void 형이어서 반환값을 사용하지 않고 상태를 처리하거나 조정한 경우, 원복을 제대로 처리해주셔야 예상하지 못한 결과를 피할 수 있습니다.

정확한 답변을 얻으려면 공유해 주신 코드를 살펴보는 것이 좋습니다. 기능적인 오류를 찾지 못했을 때는 다른 풀이 사례들을 참고하시는 것이 도움이 됩니다.

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