<Baekjoon> #21608 Simulation, 구현_상어 초등학교 c++

#21608 상어 초등학교

🦈Solution & Idea

• 모든 학생이 순서대로 (0,0)~(N-1, N-1)의 자리 중 비어있는 자리에 자신의 만족도가 가장 높은 곳에 자리를 잡는다
• 한 학생당 각각 위치에 앉았을 때 인접한 칸 중 빈 칸, 좋아하는 학생이 있는 칸에 따라 선호도가 달라지므로 각 위치를 관리하는 구조체와 이 위치간 우선순위를 정하는 compare 함수를 구현해야 한다

🦈1. Initialize

• 학생들은 자신의 번호와 좋아하는 친구 4명이 있다
• 학생들은 번호는 1번부터 주어지는 것이 아니라 student[]에는 주어지는 순서대로 들어가기 때문에 나중에 인접한 친구를 구할 때 편리하게 하기 위해 student_arr[][]를 만들었고, 여기에는 학생 번호가 1번부터 차례대로 들어간다

struct STUDENT {
	int sno;
	int prefer[4];
};
vector<STUDENT> student;
STUDENT student_arr[MAX * MAX];

• 학생이 (y,x)좌표에 자리를 잡았을 때 주변에 빈 자리와 좋아하는 친구가 몇 명인지 관리하는 구조체를 선언

struct POS_INFO {
	int y, x;
	int empty, friends;
};

• 만족도는 인접한 칸 중에서 좋아하는 학생이가장 많고, 빈 칸이 가장 많고, 행의 번호가 작고, 열의 번호가 작을 수록 높아진다

bool compare(const POS_INFO& A, const POS_INFO& B) {
	if (A.friends == B.friends)
		if (A.empty == B.empty)
			if (A.y == B.y) return A.x < B.x;
			else return A.y < B.y;
		else return A.empty > B.empty;
	else return A.friends > B.friends;
}

🦈2. Setting Seat

• vector<STUDENT> student에 저장된 학생 순서대로 자리를 탐색한다
• (0,0)~(N-1, N-1) 자리 중 아직 주인이 없는 자리부터 순서대로 탐색해보며 각 위치 좌표, 빈 공간, 인접한 친구의 수에 관한 정보를 vector<POS_INFO> pos에 넣어준다
• compare 기준으로 정렬 하여 가장 처음에 저장된 좌표 (우선 순위가 가장 높은)에 학생이 앉는다

void set_seat() {
	for (int i = 0; i < M; i++) {
		int sno = student[i].sno;
		vector<POS_INFO> pos;
		
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (map[y][x] != 0) continue;

				int neaFriends = 0, nearEmtpy = 0;

				for (int d = 0; d < 4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];

					if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

					if (map[ny][nx] == 0) nearEmtpy++;
					else {
						for (int k = 0; k < 4; k++) {
							int idx = student[i].prefer[k];
							if (map[ny][nx] == idx) {
								neaFriends++; break;
							}
						}
					}
				}
				pos.push_back({ y,x,nearEmtpy, neaFriends });
			}
		}

		sort(pos.begin(), pos.end(), compare);
		int py = pos[0].y;
		int px = pos[0].x;
		map[py][px] = sno;
	}
}

🦈3. Satisfy

• 모든 위치에 대해 하나씩 만족도를 검사해본다
• 해당 위치에 학생의 번호를 sno라 두면 studen_arr[sno]에서 해당 학생을 찾아 해당 위치에 인접한 자리에 이 학생이 선호하는 학생들 중 몇 명이나 있는지 확인해 만족도를 계산한다

int satisfy() {
	int ret = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int sno = map[i][j];
			int fnum = 0;

			for (int d = 0; d < 4; d++) {
				int ny = i + dy[d];
				int nx = j + dx[d];

				if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

				for (int k = 0; k < 4; k++) {
					int adj_sno = student_arr[sno].prefer[k];
					if (map[ny][nx] == adj_sno) {
						fnum++;
						break;
					}
				}
			}

			switch (fnum) {
			case 0: ret += 0; break;
			case 1: ret += 1; break;
			case 2: ret += 10; break;
			case 3: ret += 100; break;
			case 4: ret += 1000; break;
			}
		}
	}
	return ret;
}

🦈Source Code

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

using namespace std;

const int MAX = 21;

const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };

struct STUDENT {
	int sno;
	int prefer[4];
};
vector<STUDENT> student;
STUDENT student_arr[MAX * MAX];

struct POS_INFO {
	int y, x;
	int empty, friends;
};

int N,M;
vector<vector<int>> map;

void input() {
	cin >> N;
	M = N * N;

	map = vector<vector<int>>(N, vector<int>(N));

	for (int i = 0; i < M; i++) {
		int a, b, c, d, e;
		cin >> a >> b >> c >> d >> e;
		student.push_back({ a, {b,c,d,e} });
		student_arr[a].sno = a;
		student_arr[a].prefer[0] = b;
		student_arr[a].prefer[1] = c;
		student_arr[a].prefer[2] = d;
		student_arr[a].prefer[3] = e;
	}
}

bool compare(const POS_INFO& A, const POS_INFO& B) {
	if (A.friends == B.friends)
		if (A.empty == B.empty)
			if (A.y == B.y) return A.x < B.x;
			else return A.y < B.y;
		else return A.empty > B.empty;
	else return A.friends > B.friends;
}

int satisfy() {
	int ret = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int sno = map[i][j];
			int fnum = 0;

			for (int d = 0; d < 4; d++) {
				int ny = i + dy[d];
				int nx = j + dx[d];

				if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

				for (int k = 0; k < 4; k++) {
					int adj_sno = student_arr[sno].prefer[k];
					if (map[ny][nx] == adj_sno) {
						fnum++;
						break;
					}
				}
			}

			switch (fnum) {
			case 0: ret += 0; break;
			case 1: ret += 1; break;
			case 2: ret += 10; break;
			case 3: ret += 100; break;
			case 4: ret += 1000; break;
			}
		}
	}
	return ret;
}

void set_seat() {
	for (int i = 0; i < M; i++) {
		int sno = student[i].sno;
		vector<POS_INFO> pos;
		
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (map[y][x] != 0) continue;

				int neaFriends = 0, nearEmtpy = 0;

				for (int d = 0; d < 4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];

					if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

					if (map[ny][nx] == 0) nearEmtpy++;
					else {
						for (int k = 0; k < 4; k++) {
							int idx = student[i].prefer[k];
							if (map[ny][nx] == idx) {
								neaFriends++; break;
							}
						}
					}
				}
				pos.push_back({ y,x,nearEmtpy, neaFriends });
			}
		}

		sort(pos.begin(), pos.end(), compare);
		int py = pos[0].y;
		int px = pos[0].x;
		map[py][px] = sno;
	}
}

int main() {
	input();
	set_seat();

	cout << satisfy() << endl;

	return 0;
}