상어 초등학교 (feat. 백준, 21608번)

상어 초등학교
https://www.acmicpc.net/submit/21608

로그인

반응형

// woohyeon.kim
// https://www.acmicpc.net/submit/21608
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct Student {
	int my_num;
	int friend_num[4];
};
struct Position {
	int x, y, friend_count, empty_count;
};
int N, arr[21][21], dx[4], dy[4], result = 0;
map<int, Student> students;
inline bool cmp(const Position& v1, const Position& v2) {
	if (v1.friend_count == v2.friend_count) {
		if (v1.empty_count == v2.empty_count) {
			if (v1.x == v2.x)
				return v1.y < v2.y;
			return v1.x < v2.x;
		}
		return v1.empty_count > v2.empty_count;
	}
	return v1.friend_count > v2.friend_count;
}
inline bool is_my_friend(const int& my_friend, int(*friend_num)) {
	for (auto idx = 0; idx < 4; ++idx)
		if (friend_num[idx] == my_friend)
			return true;
	return false;
}
inline void set_seat_student(Student& student) {
	vector<Position> candidates;
	Position position;
	for (int ix = 1, iy, i, nx, ny, ii, nnx, nny; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			for (i = 0; i < 4; ++i) {
				nx = ix + dx[i], ny = iy + dy[i];
				if (1 <= nx && nx <= N && 1 <= ny && ny <= N && arr[nx][ny] == 0) {		// 주변의 빈자리 하나를 선택하고
					position.x = nx, position.y = ny, position.friend_count = position.empty_count = 0;
					// 선택된 빈자리 주변으로 친구가 있는 칸의 수와 비어있는 칸의 수를 구함
					for (ii = 0; ii < 4; ++ii) {
						nnx = nx + dx[ii], nny = ny + dy[ii];
						if (1 <= nnx && nnx <= N && 1 <= nny && nny <= N)
							if (arr[nnx][nny] == 0)										++position.empty_count;
							else if (is_my_friend(arr[nnx][nny], student.friend_num))	++position.friend_count;
					}
					candidates.push_back(position);
				}
			}
	sort(candidates.begin(), candidates.end(), cmp);
	auto& pos = candidates.front();
	arr[pos.x][pos.y] = student.my_num;
}
inline void satisfaction_survey() {
	for (int ix = 1, iy, i, nx, ny, friend_count; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy) {
			for (i = 0, friend_count = 0; i < 4; ++i) {
				nx = ix + dx[i], ny = iy + dy[i];
				if (1 <= nx && nx <= N && 1 <= ny && ny <= N)
					if (is_my_friend(arr[nx][ny], students[arr[ix][iy]].friend_num))		++friend_count;
			}
			if (friend_count == 1)
				result += 1;
			else if (friend_count == 2)
				result += 10;
			else if (friend_count == 3)
				result += 100;
			else if (friend_count == 4)
				result += 1000;
		}
	cout << result << endl;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			arr[ix][iy] = 0;
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N;
	for (int idx = 0, i, num; idx < N * N; ++idx) {
		cin >> num, students[num].my_num = num;
		for (i = 0; i < 4; ++i)
			cin >> students[num].friend_num[i];
		set_seat_student(students[num]);
	}
	satisfaction_survey();
	return 0;
}
// *&)*@*

1. 문제의 조건 1->3에 따라 순위를 결정하면 됩니다.
2. 저의 경우, sort를 위한 predicate를 정의하여 구현하였습니다.