[백준/BOJ] 백준 21608번 : 상어 초등학교

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

학생을 적절한 위치에 배치하고, 점수를 매기는 방식으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n;
vector<vector<int>> board(20, vector<int>(20, 0));
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
set<int> check[401];
int result = 0;

void Check(int number)
{
	pair<int, int> temp;
	int like_max = -1;
	int empty_max = -1;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (board[i][j] == 0)
			{
				pair<int, int> here = make_pair(i, j);
				int like_cnt = 0;
				int empty_cnt = 0;

				for (int dir = 0; dir < 4; dir++)
				{
					pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

					if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n)
					{
						if (board[there.first][there.second] == 0)
							empty_cnt++;
						else if (check[number].count(board[there.first][there.second]) != 0)
							like_cnt++;
					}
				}

				//좋아하는 학생이 인접한 칸에 더 많은 칸을 찾았을때
				if (like_max < like_cnt)
				{
					temp = here;

					like_max = like_cnt;
					empty_max = empty_cnt;
				}

				//좋아하는 학생이 인접한 칸이 최대인것의 개수와 같을때
				else if (like_max == like_cnt)
				{
					//인접한곳에 비어있는 칸이 더 많을때
					if (empty_max < empty_cnt)
					{
						temp = here;

						like_max = like_cnt;
						empty_max = empty_cnt;
					}
				}
			}
		}

	board[temp.first][temp.second] = number;
}

void Solve()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			pair<int, int> here = make_pair(i, j);
			int here_number = board[here.first][here.second];
			int like_cnt = 0; //인접한 위치에 좋아하는 학생의 수

			if (here_number == 0)
				continue;

			for (int dir = 0; dir < 4; dir++)
			{
				pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

				if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n)
				{
					//there 위치가 좋아하는 학생일때
					if (check[here_number].count(board[there.first][there.second]) != 0)
					{
						like_cnt++;
					}
				}
			}

			if (like_cnt == 4)
				result += 1000;

			else if (like_cnt == 3)
				result += 100;

			else if (like_cnt == 2)
				result += 10;

			else if (like_cnt == 1)
				result += 1;
		}
}

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

	cin >> n;

	for (int i = 0; i < n*n; i++)
	{
		int number;
		cin >> number;

		for (int j = 0; j < 4; j++)
		{
			int like;
			cin >> like;

			check[number].insert(like);
		}

		Check(number);
	}

	Solve();

	cout << result;

	return 0;
}