[백준] 상어 초등학교

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

21608번: 상어 초등학교

 

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N;
int answer;
vector<vector<int>> student; //(학생의 번호, {좋아하는 학생 번호 4개})
int board[21][21];
bool visited[21][21];

int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };

void init() {
	student = vector<vector<int>>();

	for (int i = 0; i < 21; i++) {
		memset(board[i], 0, sizeof(board[i]));
		memset(visited[i], false, sizeof(visited[i]));
	}
}

void input() {
	cin >> N;

	for (int i = 0; i < N*N; i++) {
		vector<int> v;
		int num;
		for (int j = 0; j < 5; j++) {
			cin >> num;
			v.push_back(num);
		}
		student.push_back(v);
	}
}

bool inRange(int r, int c) {
	return r >= 0 && r < N && c >= 0 && c < N;
}

vector<pair<int, int>> getCondition2(vector<pair<int, int>> &v) {
	vector<pair<int, int>> result;

	int maxValue = 0;
	for (int i = 0; i < v.size(); i++) {
		int row = v[i].first;
		int col = v[i].second;
		int cnt = 0;

		for (int d = 0; d < 4; d++) {
			int nr = row + dr[d];
			int nc = col + dc[d];

			if (inRange(nr, nc) && board[nr][nc] == 0) { //비어있는지.
				cnt++;
			}
		}

		if (maxValue < cnt) {
			maxValue = cnt;
			result = { { row,col } };
		}
		else if (maxValue == cnt) {
			result.push_back({ row,col });
		}
	}

	return result;
}

bool comp(pair<int, int> p1, pair<int, int> p2) {
	if (p1.first == p2.first)
		return p1.second < p2.second;
	else
		return p1.first < p2.first;
}

int findPos(int num) {
	for (int i = 0; i < student.size(); i++) {
		if (student[i][0] == num) {
			return i;
		}
	}
}

int getPoint(int cnt) {
	if (cnt == 0) return 0;
	else if (cnt == 1) return 1;
	else {
		return pow(10, cnt - 1);
	}
}

int getSatisfaction() {
	int result = 0;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			int num = board[r][c];
			int cnt = 0;

			for (int d = 0; d < 4; d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];

				if (inRange(nr, nc)) {
					for (int s = 1; s < 5; s++) {
						int idx = findPos(num);
						if (board[nr][nc] == student[idx][s]) {
							cnt++;
							break;
						}
					}
				}
			}

			result += getPoint(cnt);
		}
	}

	return result;
}

void print() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << board[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void solve() {
	for (int i = 0; i < student.size(); i++) {

		// 조건1.비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸 찾기.
		int condition1 = 0;
		vector<pair<int, int>> result_cond1;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				int cnt = 0; //인접 칸에 있는 좋아하는 사람 수

				if (board[r][c] == 0) { //비어있는 칸

					//인접한 칸에 좋아하는 학생있는지.
					for (int d = 0; d < 4; d++) {
						int nr = r + dr[d];
						int nc = c + dc[d];

						if (inRange(nr, nc)) { 
							for (int s = 1; s < 5; s++) {
								if (board[nr][nc] == student[i][s]) {
									cnt++;
								}
							}
							if (condition1 < cnt) {
								condition1 = cnt;
								result_cond1 = { { r,c } };
							}
							else if (condition1 == cnt) {
								result_cond1.push_back({ r,c });
							}
						}
					}
				}
			}
		}

		result_cond1.erase(unique(result_cond1.begin(), result_cond1.end()), result_cond1.end());

		//조건1 만족
		if (result_cond1.size() == 1) {
			int row = result_cond1[0].first;
			int col = result_cond1[0].second;

			board[row][col] = student[i][0];

			//print();
			continue;
		}


		//조건2. 인접한 칸 중에서 비어있는 칸이 가장 많은 칸.
		vector<pair<int,int>> result_cond2 = getCondition2(result_cond1);

		//조건2 만족
		if (result_cond2.size() == 1) {
			int row = result_cond2[0].first;
			int col = result_cond2[0].second;

			board[row][col] = student[i][0];

			//print();
			continue;
		}

		//조건3. 행 가장 작은칸 -> 열 작은칸
		sort(result_cond2.begin(), result_cond2.end(), comp);
		board[result_cond2[0].first][result_cond2[0].second] = student[i][0];

		//print();
	}

	answer = getSatisfaction();
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	init();
	input();
	solve();

	cout << answer << endl;
	return 0;
}