인프런 커뮤니티 질문&답변
작성한 질문수
4-C 질문
작성
·
172
0
안녕하세요 큰돌님
조금 다른 로직으로 풀었는데 TC랑 반례들 다 적용해보아도
다 통과되는데 제출하면 틀렸다고 해서 제가 어느부분을 놓친건지 질문드립니다.
전역변수
저는 연결정보를 다음과 같이 map과 set을 활용하였습니다.
const int INF = 987654321;
int n{};
int arPopular[15]{};
// 각 구의 인원수 저장 용도
map<int, set<int>> graph{};
// Key : 구. Value : 해당 구랑 연결된 구들
int minDiff = INF;
// 나눠진 두 구의 최소 인원수 차이구현 함수 프로토타입
// Gu - FindNode 가 서로 연결되어 있는지 여부
bool IsConnect(int Gu, int FindNode);
// 하나의 구역이 끊김 없이 연결될 수 있는지
bool IsAreaConnected(const vector<int>& Area);
// 인구수 차이 구해오기
int GetDifPop(const vector<int>& Area1, const vector<int>& Area2);
일단 저의 로직 순서는 다음과 같습니다.
비트마스킹으로 모든 경우의 수를 탐색한다.
각 경우의 수마다 비트가 0이면 vector1에다가, 1이면 vector2에다가 넣어준다.
여기까지 되었으면 일단 두 그룹으로 나뉘어진다.
각 그룹에 대해서 Union Find 알고리즘을 적용해서 서로 끊기지 않고 연결될 수 있는지 확인한다.
만약 두 그룹 모두 끊기지 않고 연결될 수 있다면 우리가 원하는 2개의 구역으로 나눈것이다.
이하 최소 찾는 로직부터는 동일.
코드 링크는 여기있습니다!
답변 1
1
큰돌
지식공유자
안녕하세요 성은님 ㅎㅎ
일단 다양하게 고쳐봤습니다...
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% 좋은 답변이지만.. 그러지 못해 죄송합니다 ㅠ
일단은 참고 부탁드립니다.
감사합니다.
큰돌
지식공유자
넵 union 부분에 문제가 있는것 같은데... 반례를 못 찾겠어요.. ㅠㅠ
찾으면 다시 답변드릴게요 ㅎㅎ
아 그리구 저부분은 union find라고 할 수 없어요... ㅎㅎ
union_find라면..
이런 식의 코드가 나와야 합니다.
struct UnionFind{
int uf[MAX];
UnionFind(){ fill(uf, uf+MAX, -1); }
int find(int a){
if(uf[a] < 0) return a;
return uf[a] = find(uf[a]);
}
bool merge(int a, int b){
a = find(a);
b = find(b);
if(a == b) return false;
uf[b] = a;
return true;
}
};
감사합니다.
헉 너무 자세한 답변 감사합니다!
1안에서 알려주신 수정 사항도 공부가 많이 되었습니다!
2안에서는 기존 코드와 차이점이 set->vector로 사용했다는 점과
union find -> dfs로 연결 여부를 판단했다는 점 인데
이게 100% 통과한거면... set 사용에 오류가 있거나, union find 알고리즘이 잘못 구현되었거나... union find로 찾을 수 없는 반례가 있는 것 같네요 ㅠㅠ..
좀 더 고민해보겠습니다!