21608 상어 초등학교

2400KB, 0ms

• 구현
• 풀이법
  • 좋아하는 학생을 bool 배열로 구현
  • 위, 왼쪽부터 좋아하는 학생 수, 비어있는 칸 확인하고 업데이트
• 주의점
  • 처음에 best_favo = 0, best_empty = 0으로 했더니 마지막 한 칸에서 자꾸 에러 남
  • 둘 다 -1로 바꿔서 갈 수 있는 칸이 한 칸밖에 없을 경우를 커버해줌

#include <iostream>
#include <cmath>

#define MAX 21
using namespace std;

bool student[MAX * MAX][MAX * MAX] = {};
int map[MAX][MAX] = {};
int order[MAX * MAX] = {};

int N;

void input() {
	int a[5];
	cin >> N;
	for (int i = 1; i <= N * N; i++) {
		cin >> a[0];
		for (int j = 1; j <= 4; j++) {
			cin >> a[j];
			student[a[0]][a[j]] = true;
		}
		order[i] = a[0];
	}
}

void solve() {
	int dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 };

	for (int i = 1; i <= N * N; i++) {
		int now = order[i];
		int best_favo = -1, best_empty = -1, best_y, best_x;

		for (int p = 0; p < N; p++) {
			for (int q = 0; q < N; q++) {
				if (map[p][q] != 0) continue;

				int favo = 0, empty = 0;
				for (int k = 0; k < 4; k++) {
					int y = p + dy[k], x = q + dx[k];
					if (y >= N || y < 0 || x >= N || x < 0) continue;
					
					if (map[y][x] == 0) empty++;
					else
						if (student[now][map[y][x]] == true) favo++;
				}

				if (favo > best_favo) {
					best_favo = favo;
					best_y = p; best_x = q;
					best_empty = empty;
				}
				else if (favo == best_favo && empty > best_empty) {
					best_favo = favo;
					best_y = p; best_x = q;
					best_empty = empty;
				}
				
			}
		}

		map[best_y][best_x] = now;
	}

	int res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int y = i + dy[k], x = j + dx[k];
				if (y >= N || y < 0 || x >= N || x < 0) continue;

				if (student[map[i][j]][map[y][x]]) cnt++;
			}

			if (cnt > 0) res += pow(10, cnt - 1);
		}
	}

	cout << res;
}

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

	input();
	solve();

	return 0;
}