백준 21608번 : 상어초등학교

sol : 74' 58''

• 수행 시간 : 4ms
• 메모리 : 2036KB

Learnings

• 사이즈 계산 잘하기. orders 사이즈를 n^2-1로 해줬어야 하는데 n으로 했다가 암살당했다.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

#define MAX_N 20
#define EMPTY 0

int n;
int grid[MAX_N + 1][MAX_N + 1];
int student_num;
int prefers[MAX_N * MAX_N + 1][4];
int orders[MAX_N * MAX_N + 1];
vector<tuple<int, int>> candidates;

int score;

// 상, 하, 좌, 우
const int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void Init() {
	cin >> n;
	student_num = n * n;

	for (int i = 0; i < student_num; i++) {
		cin >> orders[i];
		for (int j = 0; j < 4; j++) {
			cin >> prefers[orders[i]][j];
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

void FirstCond(int curS) {
	int maxCnt = 0;
	candidates.clear();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] != EMPTY) continue;

			int curCnt = 0;
			for (int d = 0; d < 4; d++) {
				int ni = i + ds[d][0], nj = j + ds[d][1];

				if (!InGrid(ni, nj)) continue;
				for (int p = 0; p < 4; p++) {
					if (grid[ni][nj] == prefers[curS][p]) {
						curCnt++;
						break;
					}
				}
			}
			if (curCnt > maxCnt) {
				maxCnt = curCnt;
				candidates.clear();
				candidates.push_back(make_tuple(i, j));
			}
			else if (curCnt == maxCnt) {
				candidates.push_back(make_tuple(i, j));
			}
		}
	}
}

void SecondCond(int curId) {
	int maxCnt = 0;
	vector<tuple<int, int>> temp;

	for (int i = 0; i < candidates.size(); i++) {
		int ci, cj;
		tie(ci, cj) = candidates[i];
		int curCnt = 0;
		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (!InGrid(ni, nj)) continue;
			if (grid[ni][nj] == EMPTY) curCnt++;
		}

		if (curCnt > maxCnt) {
			maxCnt = curCnt;
			temp.clear();
			temp.push_back(make_tuple(ci, cj));
		}
		else if (curCnt == maxCnt) {
			temp.push_back(make_tuple(ci, cj));
		}
	}

	candidates.clear();
	for (int i = 0; i < temp.size(); i++) {
		candidates.push_back(temp[i]);
	}
}



void Locate() {
	for (int order = 0; order < student_num; order++) {
		int si, sj;
		int curS = orders[order];

		// 1st Cond
		FirstCond(curS);
		if (candidates.size() == 1) {
			tie(si, sj) = candidates[0];
			grid[si][sj] = curS;
			continue;
		}
		
		// 2nd Cond
		SecondCond(curS);
		if (candidates.size() == 1) {
			tie(si, sj) = candidates[0];
			grid[si][sj] = curS;
			continue;
		}

		// 3rd Cond
		sort(candidates.begin(), candidates.end());
		tie(si, sj) = candidates[0];
		grid[si][sj] = curS;
	}
}



void GetScore(int cnt) {
	if (cnt == 0) return;
	if (cnt == 1) score += 1;
	else if (cnt == 2) score += 10;
	else if (cnt == 3) score += 100;
	else if (cnt == 4) score += 1000;
}

void VOC() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int curS = grid[i][j];
			int curCnt = 0;
			for (int d = 0; d < 4; d++) {
				int ni = i + ds[d][0], nj = j + ds[d][1];
				if (!InGrid(ni, nj)) continue;

				for (int p = 0; p < 4; p++) {
					if (grid[ni][nj] == prefers[curS][p]) {
						curCnt++;
						break;
					}
				}
			}

			GetScore(curCnt);
		}
	}

	cout << score;
}

int main() {
	Init();

	Locate();
	
	VOC();

	return 0;
}