글 읽기 - c++) 게리 맨더링2 반례, 논리 관련해서 질문드립니다.

chrismrkr 3년 전 0

문제에 있는 테스트케이스를 다 돌려봐도 결과는 똑같지만 자꾸 채점하면 틀렸습니다가 나옵니다.

코드는 아래와 같습니다.

개괄적인 코드는

1. N을 입력받고, N으로 만들 수 있는 d1, d2의 경우의 수를 모두 만들어 저장합니다.

2. 그리고 (1,1)부터 (N,N)까지 하나씩 그 지점에서 선거구를 분할할 수 있는지 확인합니다.

(is_possible_location_to_split 함수에 해당합니다.)

3. 분할할 수 있다면, split_location() 함수를 통해서 선거구를 분할합니다. 이때,

5번 선거구를 d1, d2을 이용해 반복문을 통하여 먼저 분할하면서 1,2,3,4번 선거구의 경계도 지정해줍니다.

그리고 1,2,3,4번 선거구는 BFS를 통해서 만듭니다.

4. 그리고 분할된 선거구를 2중 반복문을 통하여 인구수의 총합을 구해주고,

정렬 후 차이를 반환합니다.

이때, 위의 분할 과정에서

5 5 5

5 0 5

5 와 같은 분할이 발생할 수 있으므로 0인 경우도 5번 선거구로 함께 포함하여 합산합니다.

5. 이 과정을 반복해서 차이가 최소가 되는 값을 찾습니다.

혹시 문제접근에 대한 논리적인 이유가 있다면 꼭 꼭 답변 부탁드립니다. 또 반례도 제시해 주시면 감사하겠습니다 ㅠ

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
#define endl '\n'
#define wall -4

class location
{
public:
	int row, col;
	location(int row = 0, int col =0 ) : row(row), col(col) {}
};

int dir_row[] = { 0, 0, 1, -1 }; //동서남북
int dir_col[] = { 1, -1, 0, 0 };

int N;
int answer = 8000000;
vector<vector<int>> map;
vector<vector<int>> map_split;
vector<pair<int, int>> possible_d1_d2;
bool in_range(int row, int col) { return row >= 1 && col >= 1 && row <= N && col <= N; }
bool is_possible_location_to_split(int row, int col, int d1, int d2)
{
	bool row_check = false;
	if (1 <= row - d1 && row-d1 < row && row < row+d2 && row+d2 <= N )
	{	
		row_check = true;
	}
	bool col_check = false;
	if (1 <= col && col < col + d1 + d2 && col + d1 + d2 <= N)
	{
		col_check = true;
	}
	return row_check && col_check;
}

void clear_map_split()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++) { map_split[i][j] = 0; }
	}
}

void split_location(int row, int col, int d1, int d2)
{
	int r = row; int c = col;
	map_split[r][c] = 5;
	for (int i = c-1; i >= 1; i--) { map_split[row][i] = 3; }

	for (int i = 1; i <= d1; i++){ map_split[r-i][c + i] = 5;}
	r = r - d1; c = c + d1;

	for (int i = r-1; i >= 1; i--) { map_split[i][c] = 1; }

	for (int i = 1; i <= d2; i++) { map_split[r + i][c + i] = 5; }

	r = r + d2; c = c + d2;
	for (int i = c+1; i <= N; i++) { map_split[r][i] = 2; }

	for (int i = 1; i <= d1; i++) { map_split[r + i][c - i] = 5; }
	r = r + d1; c = c - d1;

	for (int i = r+1; i <= N; i++) { map_split[i][c] = 4; }
	for (int i = 1; i <= d2; i++) { map_split[r - i][c - i] = 5; }

	queue<location> que;
	que.push(location(row, col + 1));
	map_split[row][col + 1] = 5;
	while (!que.empty())
	{
		location current = que.front();
		que.pop();
		for (int i = 0; i < 4; i++)
		{
			int r = current.row + dir_row[i];
			int c = current.col + dir_col[i];

			if (in_range(r, c) && map_split[r][c] == 0)
			{
				map_split[r][c] = 5;
				que.push(location(r, c));
			}
		}
	}

	que.push(location(1, 1));
	map_split[1][1] = 1;
	while (!que.empty())
	{
		location current = que.front(); que.pop();

		for (int i = 0; i < 4; i++)
		{
			int r = current.row + dir_row[i];
			int c = current.col + dir_col[i];
			if (in_range(r, c) && map_split[r][c] == 0)
			{
				map_split[r][c] = 1;
				que.push(location(r, c));
			}
		}
	}

	que.push(location(1, N));
	map_split[1][N] = 2;
	while (!que.empty()) {
		location current = que.front(); que.pop();
		for (int i = 0; i < 4; i++)
		{
			int r = current.row + dir_row[i];
			int c = current.col + dir_col[i];
			if (in_range(r, c) && map_split[r][c] == 0)
			{
				map_split[r][c] = 2;
				que.push(location(r, c));
			}
		}
	}

	que.push(location(N, 1));
	map_split[N][1] = 3;
	while (!que.empty()) {
		location current = que.front(); que.pop();
		for (int i = 0; i < 4; i++)
		{
			int r = current.row + dir_row[i];
			int c = current.col + dir_col[i];
			if (in_range(r, c) && map_split[r][c] == 0)
			{
				map_split[r][c] = 3;
				que.push(location(r, c));
			}
		}
	}
		
	que.push(location(N,N));
	map_split[N][N] = 4;
	while (!que.empty()) {
		location current = que.front(); que.pop();
		for (int i = 0; i < 4; i++)
		{
			int r = current.row + dir_row[i];
			int c = current.col + dir_col[i];
			if (in_range(r, c) && map_split[r][c] == 0)
			{
				map_split[r][c] = 4;
				que.push(location(r, c));
			}
		}
	}
}
int calculate_population()
{
	vector<int> v;
	v.resize(5);
	for (int i = 0; i < v.size(); i++) { v[i] = 0; }

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (map_split[i][j] == 1) { v[0] = v[0] + map[i][j]; }
			else if (map_split[i][j] == 2) { v[1] += map[i][j]; }
			else if (map_split[i][j] == 3) { v[2] += map[i][j]; }
			else if (map_split[i][j] == 4) { v[3] += map[i][j]; }
			else if (map_split[i][j] == 5) { v[4] += map[i][j]; }
			else if (map_split[i][j] == 0) { v[4] += map[i][j]; }
			else { throw "failed"; }
		}
	}
	sort(v.begin(), v.end());
	return v[4] - v[0];
}


int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin >> N;
	for (int i = 1; i < 5; i++)
	{
		for (int j = 1; j < 5; j++)
		{
			if (i + j <= 5) { possible_d1_d2.push_back(make_pair(i, j)); }
		}
	}

	map.resize(N + 1);
	map_split.resize(N + 1);
	for (int i = 0; i < N + 1; i++) { map[i].resize(N + 1); map_split[i].resize(N + 1); }
	for (int i = 0; i < N + 1; i++)
	{
		map[i][0] = wall;
		map[0][i] = wall;
		map_split[0][i] = wall;
		map_split[i][0] = wall;
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int tmp; cin >> tmp;
			map[i][j] = tmp;
			map_split[i][j] = 0;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int k = 0; k < possible_d1_d2.size(); k++)
			{
				if (is_possible_location_to_split(i, j, possible_d1_d2[k].first, possible_d1_d2[k].second))
				{ //나눌 수 있는 위치인지 판정
					split_location(i, j, possible_d1_d2[k].first, possible_d1_d2[k].second);
					int dif = calculate_population();
					if (dif < answer) { answer = dif; }
					clear_map_split();			
				}
			}
		}
	}

	cout << answer;

}

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

문제

문제

출처

ICPC

c++) 게리 맨더링2 반례, 논리 관련해서 질문드립니다.

chrismrkr 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말