[BOJ] 21608 상어 초등학교 / C++

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int N;

struct st {
	int num;
	int friends[4];
};

struct st students[20 * 20 + 10];

int seats[20 + 10][20 + 10]; // (1, 1) ~ (N, N)

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int cur_x, cur_y;

struct cand {
	int x, y;
	int cnt_empty;
	int cnt_friends;
};

vector <cand> candidates;

bool cmp(cand &vec1, cand &vec2)
{
	if (vec1.cnt_friends > vec2.cnt_friends)
	{
		return true;
	}
	else if (vec1.cnt_friends == vec2.cnt_friends)
	{
		if (vec1.cnt_empty > vec2.cnt_empty)
		{
			return true;
		}
		else if (vec1.cnt_empty == vec2.cnt_empty)
		{
			if (vec1.x < vec2.x) return true;
			else if (vec1.x == vec2.x)
			{
				if (vec1.y <= vec2.y) return true;
				else return false;
			}
			else return false;
		}
		else return false;
	}
	else return false;
}

void choose_seats(int idx)
{
	//printf("\n>> choose_seats(%d)\n", idx);

	int num = students[idx].num;
	//printf(">> student num = %d\n", num);
	int cnt_empty = 0;
	int cnt_friends = 0;

	for (int x = 1; x <= N; x++)
	{
		for (int y = 1; y <= N; y++)
		{
			cnt_empty = 0;
			cnt_friends = 0;

			if (seats[x][y] != 0) continue; // seat already taken

			for (int k = 0; k < 4; k++)
			{
				int nx = x + dx[k];
				int ny = y + dy[k];

				if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue; // boundary

				if (seats[nx][ny] == 0) cnt_empty++;

				for (int n = 0; n < 4; n++)
				{
					if (seats[nx][ny] == students[idx].friends[n]) cnt_friends++;
				}
			}

			struct cand data = { x,y,cnt_empty,cnt_friends };
			candidates.push_back(data);
		}

	}
	/*
	for (int i = 0; i < candidates.size(); i++)
	{
		printf("[i = %d] (%d, %d) empty = %d, friends = %d\n", i, candidates[i].x, candidates[i].y, candidates[i].cnt_empty, candidates[i].cnt_friends);
	}
	*/
	// candidates 정렬

	sort(candidates.begin(), candidates.end(), cmp);
	//printf("------------------- sort -----------------------\n");
	/*
	for (int i = 0; i < candidates.size(); i++)
	{
		printf("[i = %d] (%d, %d) empty = %d, friends = %d\n", i, candidates[i].x, candidates[i].y, candidates[i].cnt_empty, candidates[i].cnt_friends);
	}
	*/

	int pos_x = candidates.front().x;
	int pos_y = candidates.front().y;
	seats[pos_x][pos_y] = num;
	//printf("seats[%d][%d] = %d\n", pos_x, pos_y, num);

	while (!candidates.empty())
	{
		candidates.pop_back();
	}
}

int calculate_score(void)
{
	int sum = 0;
	int cnt_near_friends[5] = { 0, };

	for (int i = 1; i <= N * N; i++)
	{
		int num = students[i].num;
		int cnt = 0;

		for (int x = 1; x <= N; x++)
		{
			for (int y = 1; y <= N; y++)
			{
				if (seats[x][y] == num)
				{
					for (int k = 0; k < 4; k++)
					{
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue; // boundary

						for (int n = 0; n < 4; n++)
						{
							if (seats[nx][ny] == students[i].friends[n]) cnt++;
						}
					}
				}
			}
		}
		cnt_near_friends[cnt]++;
	}


	sum = cnt_near_friends[0] * 0 + cnt_near_friends[1] * 1 + cnt_near_friends[2] * 10 + cnt_near_friends[3] * 100 + cnt_near_friends[4] * 1000;
	return sum;
}

int main(void)
{
	int answer = 0;

	scanf("%d", &N);
	for (int i = 1; i <= N * N; i++)
	{
		scanf("%d", &students[i].num);
		for (int j = 0; j < 4; j++)
		{
			scanf("%d", &students[i].friends[j]);
		}
	}

	for (int i = 1; i <= N * N; i++)
	{
		choose_seats(i);
	}

	/*
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			printf(" %d", seats[i][j]);
		}
		printf("\n");
	}
	*/
	answer = calculate_score();

	printf("%d\n", answer);
	return 0;
}

 

맘에 드는 코드는 아니지만 올리고싶어서 올려본다ㅎ