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

1. 문제 링크

문제 링크

2. 풀이

그냥 단순 구현이였습니다.
구현 기능의 순서는 이와 같습니다.

1. 입력받은 학생 순서대로 조건에 맞게 자리를 배정합니다.
2. 만족도를 합산합니다.

3. 전체 코드

#define MAX 20
#include <bits/stdc++.h>

using namespace std;

int n;
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
int order[MAX * MAX + 1];
int st[MAX * MAX + 1][4];
int seat[MAX][MAX];
int score[5] = { 0, 1, 10, 100, 1000 };

bool isOut(int nr, int nc) {
	return nr < 0 || nr >= n || nc < 0 || nc >= n;
}

bool isLikeSt(int seatNum, int stNum) {
	return seatNum == st[stNum][0] || seatNum == st[stNum][1] || seatNum == st[stNum][2] || seatNum == st[stNum][3];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n * n; i++) {
		cin >> order[i];

		for (int j = 0; j < 4; j++) {
			cin >> st[order[i]][j];
		}
	}

	for (int i = 0; i < n * n; i++) {
		int stNum = order[i];
		int maxLikeCount = 0;
		int maxEmptyCount = 0;
		int seatY = n;
		int seatX = n;

		for (int r = 0; r < n; r++) {
			for (int c = 0; c < n; c++) {
				// 이미 앉아있는 자리
				if (seat[r][c] > 0) continue;

				int likeCount = 0;
				int emptyCount = 0;

				for (int dir = 0; dir < 4; dir++) {
					int nr = r + my[dir];
					int nc = c + mx[dir];

					if (isOut(nr, nc)) continue;

					// 비어있을 때
					if (seat[nr][nc] == 0) {
						emptyCount++;
						continue;
					}

					// 좋아하는 학생일 때
					if (isLikeSt(seat[nr][nc], stNum)) {
						likeCount++;
					}
				}

				// 좋아하는 학생이 더 많이 인접했을 때
				if (likeCount > maxLikeCount) {
					maxLikeCount = likeCount;
					maxEmptyCount = emptyCount;
					seatY = r;
					seatX = c;
				}
				// 좋아하는 학생 인접수가 같을 때
				else if (likeCount == maxLikeCount) {
					// 빈 칸이 더 많을 때
					if (emptyCount > maxEmptyCount) {
						maxEmptyCount = emptyCount;
						seatY = r;
						seatX = c;
					}
					// 빈 칸이 같고 행이 작거나, 행이 같아도 열이 작을 때
					else if (emptyCount == maxEmptyCount && (r < seatY || (r == seatY && c < seatX))) {
						seatY = r;
						seatX = c;
					}
				}
			}
		}

		seat[seatY][seatX] = stNum;
	}

	// 합산
	int ans = 0;

	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			int stNum = seat[r][c];
			int likeCount = 0;

			for (int dir = 0; dir < 4; dir++) {
				int nr = r + my[dir];
				int nc = c + mx[dir];

				if (isOut(nr, nc)) continue;

				if (isLikeSt(seat[nr][nc], stNum)) {
					likeCount++;
				}
			}

			ans += score[likeCount];
		}
	}

	cout << ans;

	return 0;
}