BOJ 21608번: 상어 초등학교

문제

문제 바로가기> BOJ 21608번: 상어 초등학교

21608번: 상어 초등학교

 

풀이

문제를 풀 때 중요하다고 느낀 점을 몇가지 적어보겠다.

 

1. 자리를 정할 때 우선순위 별로 정렬하기 위해 priority_queue를 이용

   * 이때, 구조체 내 연산자 재정의 방법을 알고 있어야 한다.

      (좋아하는 학생 수 > 빈칸 > 작은 행 번호 > 작은 열 번호) 우선으로 연산자 재정의를 해주어야 하기 때문!

 

2. 이미 자리가 정해진 경우 continue 해주기

    이미 자리가 정해졌는데, 그 자리를, pq 에 넣을 필요가 없다. 오히려 덮어씌워질 우려가,,

 

3. order_to_num 배열을 이용해 학생의 순서와 번호를 매핑 시켜주기!

    주어진 순서(!=번호)대로 자리를 배정하고, 

    나중에 만족도를 구할 때, 어느 학생(학생 번호)이 어디 앉았는지 알고 있어야 하기 때문!

 

#include<iostream>
#include<vector>
#include<queue>
#define MAX 21
#define MAX2 450
#define EMPTY 0
using namespace std;

struct DATA {
	int like, empty, row, col;

	bool operator < (const DATA &d) const {
		if (like == d.like) {
			if (empty == d.empty) {
				if (row == d.row) return col > d.col; // 열의 번호가 가장 작은 칸
				return row > d.row; //  행의 번호가 가장 작은 칸
			} return empty < d.empty; // 인접한 칸 중에서 비어있는 칸이 가장 많은 칸
		} return like < d.like; // 좋아하는 학생이 인접한 칸에 가장 많은 칸
	}
};

int N;
int seat[MAX][MAX];
int order_to_num[MAX2];
vector<int> student[MAX2];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int satisfy[] = { 0, 1, 10, 100, 1000 };

void input() {
	cin >> N;

	int n, s;
	for (int i = 0; i < N*N; i++) {
		cin >> n; // 학생의 번호
		order_to_num[i] = n;
		for (int j = 0; j < 4; j++) { // 그 학생이 좋아하는 학생 4명의 번호
			cin >> s;
			student[n].push_back(s);
		}
	}
}

void set_seat(int num) {

	priority_queue<DATA> pq;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (seat[y][x]) continue; // 이미 주인이 있는 자리
			int like = 0, empty = 0;
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue; // 범위를 벗어나는 경우
				for (int l = 0; l < 4; l++) { // 좋아하는 학생
					if (seat[ny][nx] == student[num][l]) like++;
				}
				if (seat[ny][nx] == EMPTY) empty++; // 빈자리
			}
			pq.push({ like, empty, y, x });
		}
	}
	seat[pq.top().row][pq.top().col] = num;
}

void get_satisfy() {
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int like = 0;
			int num = seat[i][j];
			for (int d = 0; d < 4; d++) {
				int ny = i + dy[d];
				int nx = j + dx[d];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				for (int l = 0; l < 4; l++) {
					if (seat[ny][nx] == student[num][l]) like++;
				}
			}
			ans += satisfy[like];
		}
	} cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	for (int i = 0; i < N * N; i++) set_seat(order_to_num[i]);
	get_satisfy();
}