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

안녕하세요 성은님 ㅎㅎ

일단 다양하게 고쳐봤습니다...

1안.

고친 부분은 다음과 같습니다.

	for (int i = 1; i <= n; i++)  
	{ 
		set<int> sTmp{};
		graph.insert({ i, sTmp }); 
	}
	int ConnectCount{};
	for (int i = 1; i <= n; i++) // 1번 구부터 시작
	{
		cin >> ConnectCount;  
		int ConnectNode{};
		for (int j = 0; j < ConnectCount; j++)
		{
			cin >> ConnectNode;
			graph[i].insert(ConnectNode);
			graph[ConnectNode].insert(i);
		}
	}

애초부터 양방향 간선을 만드는게 좋습니다.

bool IsConnect(int Gu, int FindNode)
{
	  
	auto iter = graph[Gu].find(FindNode);
	if(iter == graph[Gu].end())return false; 

	return true;
}

연결되어있는 부분 이렇게 하는게 맞지 않을까요? 해당 idx에 연결되어있는 것과.. 되니까요.

연결되어있는 함수의 의미가 이렇게 하는게 맞지 않나 싶어서 이것도 고쳐봤습니다.

	for (int i = 0; i < (int)Area.size(); i++)
	{
		int curNode = Area[i];
		for (int j = i + 1; j < (int)Area.size(); j++)
		{
			int nextNode = Area[j];
			// 의미가 명확히
			if (IsConnect(curNode, nextNode))
			{
				int mn = min(Union[curNode], Union[nextNode]);
				Union[curNode] = mn;
				Union[nextNode] = mn; 
			}
		}
	}
	set<int> temps;
	for(int idx : Area){
		temps.insert(Union[idx]);
	} 
	if(temps.size() >= 2) return false; 
	return true;

고친 코드는 다음과 같습니다.

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

const int INF = 987654321;

int n{};
int arPopular[15]{}; // 각 구의 인원수 저장 용도
map<int, set<int>> graph{}; // Key : 구. Value : 해당 구랑 연결된 구들 
int minDiff = INF; // 나눠진 두 구의 최소 인원수 차이

bool IsConnect(int Gu, int FindNode);
bool IsAreaConnected(const vector<int>& Area);
int GetDifPop(const vector<int>& Area1, const vector<int>& Area2);

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

	cin >> n;
	for (int i = 1; i <= n; i++) // 1번 구부터 시작
	{
		cin >> arPopular[i];
	} 
	// 양방향 간선 구현
	for (int i = 1; i <= n; i++)  
	{ 
		set<int> sTmp{};
		graph.insert({ i, sTmp }); 
	}
	int ConnectCount{};
	for (int i = 1; i <= n; i++) // 1번 구부터 시작
	{
		cin >> ConnectCount;  
		int ConnectNode{};
		for (int j = 0; j < ConnectCount; j++)
		{
			cin >> ConnectNode;
			graph[i].insert(ConnectNode);
			graph[ConnectNode].insert(i);
		}
	}

	// 모든 구 나누기 경우의 수 탐색 (연결 안되든 되든) 
	for (int i = 1; i < (1 << n) - 1; i++)
	{
		vector<int> v0_Gu{};
		vector<int> v1_Gu{};

		// 구역별로 넣어준다. 
		for (int j = 0; j < n; j++)
		{
			if ((i & (1 << j)))
				v1_Gu.push_back(j + 1);
			else
				v0_Gu.push_back(j + 1);
		}

		if (IsAreaConnected(v0_Gu) && IsAreaConnected(v1_Gu))
		{
			// 두 구역 각각이 모두 연결되어있음. 
			int CurDiff = GetDifPop(v0_Gu, v1_Gu); // 인구차 구하기
			minDiff = min(minDiff, CurDiff); // 인구차 갱신
		}
	}
	
	if (minDiff == INF)
		minDiff = -1;
	cout << minDiff << "\n";
}

bool IsConnect(int Gu, int FindNode)
{
	  
	auto iter = graph[Gu].find(FindNode);
	if(iter == graph[Gu].end())return false; 

	return true;
}

bool IsAreaConnected(const vector<int>& Area)
{
	// 모든 구를 탐색하는데 하나의 구라도 하나라도 연결 안되어있으면 false
	// 만약 Area에 구가 하나밖에 없으면 걍 true
	if (Area.size() == 1)
		return true;

	int Union[15]{};
	for(int idx : Area){
		Union[idx] = idx;
	}  

	for (int i = 0; i < (int)Area.size(); i++)
	{
		int curNode = Area[i];
		for (int j = i + 1; j < (int)Area.size(); j++)
		{
			int nextNode = Area[j];
			// 의미가 명확히
			if (IsConnect(curNode, nextNode))
			{
				int mn = min(Union[curNode], Union[nextNode]);
				Union[curNode] = mn;
				Union[nextNode] = mn; 
			}
		}
	}
	set<int> temps;
	for(int idx : Area){
		temps.insert(Union[idx]);
	} 
	if(temps.size() >= 2) return false; 
	return true;
}

int GetDifPop(const vector<int>& Area1, const vector<int>& Area2)
{
	int sum1{};
	int sum2{};

	for (auto Gu : Area1)
	{
		sum1 += arPopular[Gu];
	}
	for (auto Gu : Area2)
	{
		sum2 += arPopular[Gu];
	}

	return abs(sum1-sum2);
}

근데 이게 8%에서 틀리더라구요. 원래는 2%였는데 그래도 발전하긴했는데 부족한 것 같습니다..

2안.

문제가 뭔지는 모르겠고

그럴 때 제가 하는 방법이 있는데 뭔가를 좀 크게 바꿔서 다시 짜보는겁니다.

저는 성은님의 코드 중에 set부분, connect부분을 크게 바꿔서 다시 짜봤습니다.

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

const int INF = 987654321;

int n{};
int arPopular[15]{};
map<int, vector<int>> graph{};  
int minDiff = INF;
  
void dfs(int node, vector<bool>& visited, const vector<int>& area) {
    visited[node] = true;
    for (int adj : graph[node]) {
        if (!visited[adj] && find(area.begin(), area.end(), adj) != area.end()) {
            dfs(adj, visited, area);
        }
    }
}

bool IsAreaConnected(const vector<int>& area) {
    if (area.empty()) return false;
    vector<bool> visited(n + 1, false);
    dfs(area[0], visited, area);  

    for (int node : area) {
        if (!visited[node]) return false;  
    }
    return true;
}

int GetDifPop(const vector<int>& area1, const vector<int>& area2) {
    int sum1 = accumulate(area1.begin(), area1.end(), 0, [&](int sum, int node) { return sum + arPopular[node]; });
    int sum2 = accumulate(area2.begin(), area2.end(), 0, [&](int sum, int node) { return sum + arPopular[node]; });
    return abs(sum1 - sum2);
}

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

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

    for (int i = 1; i <= n; i++) {
        int connectCount, connectNode;
        cin >> connectCount;
        while (connectCount--) {
            cin >> connectNode;
            graph[i].push_back(connectNode);
            graph[connectNode].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);
        }

        if (IsAreaConnected(area1) && IsAreaConnected(area2)) {
            int curDiff = GetDifPop(area1, area2);
            minDiff = min(minDiff, curDiff);
        }
    }

    cout << (minDiff == INF ? -1 : minDiff) << "\n";
}

이렇게 하면 통과합니다.

문제가 뭔지를 알려줘야 100% 좋은 답변이지만.. 그러지 못해 죄송합니다 ㅠ

일단은 참고 부탁드립니다.

감사합니다.