글 읽기 - 제가 놓치고 있는 부분이 무엇인지 모르겠습니다.

skyjpower 4년 전 0

제 생각한 풀이방법은

[0번 구역이 포함된 선거구 vs 0번 구역이 포함되지 않은 선거구]

로 나누고, 0번 구역에 연결된 구역들을 하나씩 선거구에 추가해보면서 인구 차이를 계산하는 것입니다.

인구 차이는

[0번 구역이 포함된 선거구 - 0번 구역이 포함되지 않은 선거구]

와 같이 계산하며, 이 값이 0보다 크거나 같은 경우를 가지치기 했습니다.

선거구가 두 개로 나누어 질 수 있는 지는 bfs를 통해 판단했습니다.

제가 생각한 것 중에 잘못된 것이 있는지 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

#define INF 999999999

int		arrPopulation[20] = { 0 }; // 각 구역의 인구수
int		g_nTownCnt = 0;            // 총 구역의 수
int		g_nMin = INF;              // 최소 인구 차이

vector<vector<int>>	vvecTownRelation; // 각 구역별 연결되어있는 구역 리스트

void Input()
{
	// 구역의 개수
	scanf("%d", &g_nTownCnt);
	// 각 구역의 인구수
	for (int i = 0; i < g_nTownCnt; ++i)
		scanf("%d", &arrPopulation[i]);

	// 각 구역별로 이어져 있는 구역 저장
	vvecTownRelation.resize(g_nTownCnt);
	for (int i = 0; i < g_nTownCnt; ++i)
	{
		int n; scanf("%d", &n);
		for (int j = 0; j < n; ++j)
		{
			int t; scanf("%d", &t);
			vvecTownRelation[i].push_back(t - 1);
		}
	}
}

/*	< bTown 배열 설명 >
	true : 0번 구역이 포함된 선거구
	false : 0번 구역이 포함되지 않은 선거구
*/
bool bTown[20] = { false };

/*	< Check() 함수 설명 >
	두 선거구로 나누기가 가능한 경우,
		(0번 구역이 포함된 선거구의 인구수 - 0번 구역이 포함되지 않은 인구수) 를 리턴
	두 선거구로 나누기가 불가능한 경우,
		INF를 리턴
*/
int Check()
{
	bool bTemp[20] = { false };
	int nLeft = 0, nRight = 0;	// Left : 0번 구역을 포함한 선거구, Right : 0번 구역을 포함하지 않는 선거구
	int nTownIdx = -1;		// 0번 구역이 포함되지 않은 선거구 중 아무 구역을 가리킬 인덱스
	int nRemainTown = 0;	// 0번 구역이 포함되지 않은 선거구에 포함된 구역의 수

	for (int i = 0; i < g_nTownCnt; ++i)
	{
		bTemp[i] = bTown[i];
		if (!bTown[i])
		{
			nTownIdx = i;
			nRemainTown++;
			nRight += arrPopulation[i];
		}
		else
		{
			nLeft += arrPopulation[i];
		}
	}

	if (nRemainTown == 0)
		return INF;

	queue<int> q;
	q.push(nTownIdx);
	bTemp[nTownIdx] = true;

	while (!q.empty())
	{
		int cur_town = q.front();
		q.pop();
		nRemainTown--;

		for (int i = 0; i < vvecTownRelation[cur_town].size(); ++i)
		{
			int near_town = vvecTownRelation[cur_town][i];
			if (!bTemp[near_town])
			{
				q.push(near_town);
				bTemp[near_town] = true;
			}
		}
	}

	if (nRemainTown == 0)
		return nLeft - nRight;
	else
		return INF;
}

void dfs(int townIdx)
{
	int diff = Check();
	if (diff != INF)
	{
		int absDiff = abs(diff);
		if (absDiff < g_nMin)
			g_nMin = absDiff;

		// Right 선거구가 인구 수가 더 많아진 경우
		if (diff >= 0)
			return;
	}

	for (int i = 0; i < vvecTownRelation[townIdx].size(); ++i)
	{
		int next_town = vvecTownRelation[townIdx][i];
		if (bTown[next_town])
			continue;

		bTown[next_town] = true;
		dfs(next_town);
		bTown[next_town] = false;
	}
}

void Solution()
{
	bTown[0] = true;
	dfs(0);
}

void PrintResult()
{
	if (g_nMin == INF)
		printf("-1\n");
	else
		printf("%d\n", g_nMin);
}

int main()
{
	Input();
	Solution();
	PrintResult();
	
	return 0;
}

전체적인 로직은 제가 짰던 방식과 같습니다. 우선 말씀하신 부분으로 판단하자면 한 구역에 한해서만 연결 요소를 판단하시고 다른 구역에는 하시지 않은 것으로 보입니다. 저 같은 경우는 우선 두 구역을 질문자님과 같은 방식으로 나누었고 두 구역 모두 DFS로 탐색을 해주었습니다. (BFS 쓰셔도 무방합니다) DFS를 다시 한번 돌릴 때는 체크배열을 초기화를 해주고 돌렸습니다. (중복 부분 제거). 그리고 DFS 부분은 딱 연결요소만 판단하기 위해서 따로 함수로 빼주었습니다. 지금 바빠서 직접 돌려보지 못하였으니 제가 말씀드린 부분과 질문자님이 생각하신 부분이 다르시다면 댓글 부탁드립니다.

skyjpower 4년 전 0

안녕하세요. 답글 감사합니다!

말씀 중에 "한 구역에 한해서만 연결 요소를 판단하시고 다른 구역에는 하시지 않은 것으로 보입니다" 부분에서는,

DFS() 함수는 0번 구역을 기준으로 0번 구역과 연결될 수 있는 구역들을 하나씩 추가해주고 있는 함수입니다. 따라서 0번 구역이 포함된 선거구는 서로 연결되어 있다라고 가정하고

그 외의 구역들( 0번 구역이 포함된 선거구에 속하지 않은 구역들 ) 이 서로 연결될 수 있는 지만 판단하고 있습니다. 여기서 문제가 발생했을까요?

danimartinwife 4년 전 1

게시판에 새로 올라온 반례 돌려보니까,

10
1 2 3 4 5 6 7 8 9 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 1

정답은 1인데 35가 나왔습니다.

"0이 포함된 선거구는 서로 연결되어있다고 가정" 여기서 잘못되었습니다. 0이 포함된 구역들도 연결되었는지 따로 확인하셔야 합니다.

skyjpower 4년 전 0

반례 찾아주셔서 정말 감사합니다! 집에 가서 문제점을 찾아 해결해보겠습니다.

DFS돌릴 때 0번 구역과 연결되어 있는 구역들만 추가하고 있는데도 서로 연결되어 있지 않는 경우가 나올 수 있다는 것인가요?

skyjpower 4년 전 0

말씀해주신 예외는 Input() 함수에서 vvecTownRelation[i].push_back(t - 1); 밑에 vvecTownRelation[t - 1].push_back(i); 를 해주어 양방통행으로 열어주자

답이 1로 나왔습니다. 이외에도 문제가 있어 아직 답이 아니지만, 덕분에 Input()에서도 실수가 있다는 것을 발견했습니다. 감사합니다!

kjw13 3년 전 1

1 2 3 4 5 6 7 8 9 10

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

1 1

이 예시가 올바른 예시인가요...?

1번이 2번과 인접하면 2번역시 1번과 인접하다는 표시를 해야하는 것 아닌가요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 놓치고 있는 부분이 무엇인지 모르겠습니다.

skyjpower 4년 전 0

danimartinwife 4년 전 1

skyjpower 4년 전 0

danimartinwife 4년 전 1

skyjpower 4년 전 0

skyjpower 4년 전 0

kjw13 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말