4-C 어느 부분이 틀렸는지 모르겠습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-C와 다양한 타입의 함수

해결된 질문

작성

https://www.acmicpc.net/source/share/e76dff0067f048f28c1a105de7d81014

강의를 봤는데도 코드가 왜 틀린건지 잘 이해가 안되네요.
테케는 통과했는데, 2%에서 틀립니다. 리뷰 부탁드립니다!

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 곰다님 ㅎㅎ

전체적인 로직은 너무나 잘 짜쎴네요 ㅎㅎ

다만, 해당 코드를 제가 다듬어봤습니다.

이렇게 하시면 됩니다. :)

참고부탁드립니다.

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

int iN, iMin = INT_MAX;
int Population[11];
vector<int> Adj[11];
bool Visited[11];

void Solve(int node, int check, int &able)
{
    for (int adj : Adj[node])
    {
        if ((check & (1 << adj)) && !Visited[adj])
        {
            Visited[adj] = true;
            able |= (1 << adj);
            Solve(adj, check, able);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);

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

    for (int i = 1; i <= iN; ++i)
    {
        int iTemp, iDest;
        cin >> iTemp;
        while (iTemp--)
        {
            cin >> iDest;
            Adj[i].push_back(iDest);
            Adj[iDest].push_back(i);  
            // 양방향간선을 정확히 만들어야 합니다.
        }
    }

    for (int i = 1; i < (1 << iN); ++i) 
    {
        int iArea1 = 0, iArea2 = 0;
        int iStart1 = 0, iStart2 = 0;
        int iSum1 = 0, iSum2 = 0;
        
        for (int j = 0; j < iN; ++j)
        {
            if (i & (1 << j))
            {
                iSum1 += Population[j + 1];
                iArea1 |= (1 << (j + 1));
                if (iStart1 == 0)
                {
                    iStart1 = j + 1;
                }
            }
            else
            {
                iSum2 += Population[j + 1];
                iArea2 |= (1 << (j + 1));
                if (iStart2 == 0)
                {
                    iStart2 = j + 1;
                }
            }
        }

        if (iStart1 == 0 || iStart2 == 0)
        {
            continue;
        }

        if (iMin > abs(iSum1 - iSum2))
        {
            int iAble = 0;
            memset(Visited, 0, sizeof(Visited));
            Visited[iStart1] = true;
            iAble |= (1 << iStart1);
            Solve(iStart1, iArea1, iAble);

            if (iArea1 != iAble)
            {
                continue;
            }

            iAble = 0;
            memset(Visited, 0, sizeof(Visited));
            Visited[iStart2] = true;
            iAble |= (1 << iStart2);
            Solve(iStart2, iArea2, iAble);

            if (iArea2 != iAble)
            {
                continue;
            }

            iMin = abs(iSum1 - iSum2);
        }
    }

    if (iMin == INT_MAX)
    {
        cout << -1;
    }
    else
    {
        cout << iMin;
    }

    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

곰다

질문자

답변 감사합니다 선생님! 몇 가지 질문하고 싶습니다.

1. 양방향 간선은 입력단계에서 자연스럽게 만들어지는 거 아닌가요?

    for (int i = 1; i <= iN; ++i)
    {
        int iTemp, iDest;
        cin >> iTemp;
        while (iTemp--)
        {
            cin >> iDest;
            Adj[i].push_back(iDest);
            Adj[iDest].push_back(i);  
            // 양방향간선을 정확히 만들어야 합니다.
        }
    }

'단방향 간선이 있을 수 있다' 라면 틀린 이유가 납득되는데, 문제 및 작성하신 코드를 보니 주어지는 간선은 모두 양방향 간선으로 보입니다. 예를 들어 3과 5가 연결되어 있다면 for문에서 i가 3일 때 Adj[5].push_back(3); 이 부분은 필요없이 i가 5일 때 처리되는거 아닌가요?

2. 저는 int Adj[11]; 형태로 인접 리스트도 비트마스킹으로 나타내려 했는데 이러면 인접한 수들만 순회가 아니라 1 ~ iN 중 켜져있는 비트를 찾아서 순회라서 바꿔서 사용하신건가요?

3. 문제와 별개로 비트마스킹을 사용해야겠다라고 떠올리시는 단계가 어느 부분인지 궁금합니다. 이전 강의들에서 말씀하신 완탐 - Bfs,Dfs - 그리디 순의 단계처럼 따로 생각하시는 포인트가 있는지 궁금하네요. (4-A에서 비트마스킹 쉽네!했다가 4-B에서 털려서 알고 가야 편하겠다는 생각이 들어 질문합니다 ㅎ.. ㅠ)

큰돌

지식공유자

안녕하세요 곰다님 ㅎㅎ

Q1 >> 아 네 맞습니다. 이 문제같은 경우 그렇게 하셔도 됩니다. 제가 착각했습니다. ㅠ

Q2 >> 질문이 좀 모호한데요.

저는 int Adj[11]; 형태로 인접 리스트도 비트마스킹으로 나타내려 해도 될까요? 라는 질문인가요? -> 그러셔도 됩니다. 다만 저는 인접리스트가 더 편하다고 생각합니다. 굳이 모든 정점을 탐색하지 않아도 되니까요.

Q3. >>

음... 여러개의 경우의 수 -> 조합을 좀 더 깔끔하게 풀고자 해서 -> 비트마스킹을 한 것이라고 보면 됩니다. nC1, nC2, nC3 ... 의 모든 경우의 수 ? -> 깔끔하게 비트마스킹으로 시도해볼까? -> 어? 이거 문제범위가 어느정도지? -> N이 10이네..?30이하면 비트마스킹으로 가능하다고 했지? -> 고고

이런 플로우입니다. ㅎㅎ

감사합니다.

곰다

질문자

상세한 답변 감사합니다! 강의 너무 잘보고 있습니다.

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

4-C 어느 부분이 틀렸는지 모르겠습니다.