백준 - 상어 초등학교 (21608번)

백준 - 상어 초등학교 (21608번)

크게 어렵지 않은 난이도의 구현 문제이다.

대충 짜느라 코드도 좀 더럽고 비효율적이긴한데, 주변에 좋아하는 학생의 갯수를 구하는 로직이랑 빈공간을 구하는 로직을 한 번에 할 수 있을 것 같다.

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

using namespace std;

typedef struct __pos {
	int row;
	int col;
}pos;

int n;
int student_info[500][6];
int empty_map[500][500];
int student_map[500][500];
pos seat_info[500];

int rowDir[4] = { -1, 0, 1, 0 };
int colDir[4] = { 0, 1, 0, -1 };

const inline bool is_safe(int row, int col)
{
	if (row < 0 || row > n - 1 || col < 0 || col > n - 1)
		return false;
	return true;
}

pos get_by_like(int student_idx)
{
	int most_like = -1;
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			// 현재 자리에 다른 학생이 있음
			if (empty_map[row][col] == 1)
				continue;

			// 현재 자리를 기준으로 상하좌우에 좋아하는 학생이 있는지 몇명인지 체크
			int like = 0;
			for (int k = 0; k < 4; k++) {
				int nrow = row + rowDir[k];
				int ncol = col + colDir[k];
				if (!is_safe(nrow, ncol))
					continue;
				
				for (int p = 1; p < 5; p++) 
					if (student_map[nrow][ncol] == student_info[student_idx][p]) {
						like++;
						break;
					}
			}
			if (like)
				most_like = max(like, most_like);
		}
	}

	pos idx = { -1, -1 };
	if (most_like == -1)
		return idx;

	vector<pos> candidate;

	// 후보군을 모음
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (empty_map[i][j])
				continue;

			int like = 0;
			for (int k = 0; k < 4; k++) {
				int nrow = i + rowDir[k];
				int ncol = j + colDir[k];
				if (!is_safe(nrow, ncol))
					continue;

				if (student_map[nrow][ncol] == 0)
					continue;

				for (int p = 1; p < 5; p++)
					if (student_map[nrow][ncol] == student_info[student_idx][p]) {
						like++;
						break;
					}
			}
			if (like == most_like)
				candidate.push_back({ i, j });
		}
	}
	// 만약 1명뿐이면 바로 리턴이 가능
	if (candidate.size() == 1)
		return candidate[0];

	// 1명 이상이라면 row, col이 가장 작은 것을 리턴해야함
	int empty_cnt_map[21][21];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) 
			empty_cnt_map[i][j] = 0;
		
	for (int i = 0; i < candidate.size(); i++) {
		pos cur = candidate[i];
		for (int k = 0; k < 4; k++) {
			int nrow = cur.row + rowDir[k];
			int ncol = cur.col + colDir[k];
			if (!is_safe(nrow, ncol))
				continue;
			if (empty_map[nrow][ncol]) 
				continue;
			empty_cnt_map[cur.row][cur.col]++;
		}
	}

	int max_cnt = 0;
	for (int i = 0; i < candidate.size(); i++) {
		pos cur = candidate[i];
		max_cnt = max(empty_cnt_map[cur.row][cur.col], max_cnt);
	}
	for (int i = 0; i < candidate.size(); i++) {
		pos cur = candidate[i];
		if (empty_cnt_map[cur.row][cur.col] == max_cnt) 
			return cur;
	}
	return idx;
}

pos get_by_empty()
{
	int most_empty = -1;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) {
			if (empty_map[i][j])
				continue;
			int empty = 0;
			for (int k = 0; k < 4; k++) {
				int nrow = i + rowDir[k];
				int ncol = j + colDir[k];
				if (!is_safe(nrow, ncol))
					continue;
				if (empty_map[nrow][ncol] == 0) 
					empty++;
			}
			most_empty = max(most_empty, empty);
		}

	pos idx = { -1, -1 };
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) {
			if (empty_map[i][j])
				continue;
			int empty = 0;
			for (int k = 0; k < 4; k++) {
				int nrow = i + rowDir[k];
				int ncol = j + colDir[k];
				if (!is_safe(nrow, ncol))
					continue;
				if (empty_map[nrow][ncol] == 0)
					empty++;
			}
			if (empty == most_empty)
				return { i, j };
		}
			
	return idx;
}
void seat_student(pos seat, int student, int student_idx)
{
	empty_map[seat.row][seat.col] = 1;
	student_map[seat.row][seat.col] = student;
	seat_info[student_idx] = { seat.row, seat.col };
}

int answer = 0;
void solve()
{
	for (int i = 0; i < n * n; i++) {
		pos idx = get_by_like(i);
		if (idx.row == -1) 
			idx = get_by_empty();
		seat_student(idx, student_info[i][0], i);
	}
	int like_arr[5] = { 0, 1, 10, 100, 1000 };
	for (int i = 0; i < n * n; i++) {
		int like = 0;
		pos idx = seat_info[i];
		for (int k = 0; k < 4; k++) {
			int nrow = idx.row + rowDir[k];
			int ncol = idx.col + colDir[k];
			if (!is_safe(nrow, ncol))
				continue;

			for (int p = 1; p < 5; p++) 
				if (student_map[nrow][ncol] == student_info[i][p]) {
					like++;
					break;
				}
		}
		answer += like_arr[like];
	}
}
int main(void)
{
	cin >> n;
	for (int i = 0; i < n * n; i++) 
		cin >> student_info[i][0] >> student_info[i][1] >> student_info[i][2] >> student_info[i][3] >> student_info[i][4];

	solve();
	cout <<  answer << "\n";

	return 0;
}