BOJ 21608 : 상어 초등학교

#BOJ 21608 : 상어 초등학교

21608번: 상어 초등학교

 

#풀이

격자판 위에 학생들을 조건에 맞게 배치하는 문제이다.

우선순위에 맞게 학생들을 배치 해야 한다.

 

나는 먼저 격자 한 칸에 대한 데이터를 저장하는 구조체를 만들고

구조체 멤버 변수는 좋아하는 사람의 개수 , 빈칸의 개수, 행이 작음, 열이 작음 이다.

 

우선순위는

 

인접한 칸의 좋아하는 사람의 개수 > 빈칸의 개수 > 행이 작음 > 열이 작음 이므로

 

우선순위큐에서 사용할 cmp 클래스를 이에 걸맞게 만들었다.

 

그 후 답을 구하면 어렵지 않다.

 

#코드

#include<iostream>
#include<queue>
#include<vector>

#define second X;
#define first Y;
using namespace std;
int board[21][21];
int stu[401][5];
int N;
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
int ans;
struct board_data { // 칸 데이터
	int x = 0; // 칸 좌표
	int y = 0;
	int board_null = 0; // 인접한 칸의 빈 칸의 개수
	int like = 0; // 인접한 칸의 좋아하는 번호 개수
}typedef board_data;

class cmp {
public:
	bool operator () (board_data a, board_data b) { // 우선순위 큐 비교 함수를 만듬  문제 나온 우선순위 좋아하는 사람, 빈 공간, 행, 열 
		if (a.like > b.like) return false; // true는 b가 앞으로 false 는 a가 앞으로
		else if(a.like == b.like){
			if (a.board_null > b.board_null) return false;
			else if(a.board_null == b.board_null){
				if (a.x < b.x) return false;
				else if(a.x == b.x){
					if (a.y < b.y) return false;
				}
			}
		}
		return true;
	}
};
priority_queue<board_data, vector<board_data>, cmp> q;
void locate(int num) {
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (board[i][j] != 0) continue; // 내가 선택하려는 칸이 이미 선택되어 있는 경우
			board_data data;	
			for (int r = 0; r < 4; r++) { //인접한 칸 조사
				int x = dx[r] + i;
				int y = dy[r] + j;

				if (x < 1 || y < 1 || x > N || y > N) continue; // 범위 나감
				
				if (stu[num][1] == board[x][y] || stu[num][2] == board[x][y] || stu[num][3] == board[x][y] || stu[num][4] == board[x][y]) { // 인접한 칸의 좋아하는 번호 개수
					data.like++;
					continue;
				}

				if (board[x][y] == 0) data.board_null++; // 빈칸 개수

				
			}

			data.x = i;
			data.y = j;
			q.push(data); 
		}
		
	}
	if (q.empty()) return;
	board_data loc = q.top();
	board[loc.x][loc.y] = num;
	while (!q.empty()) q.pop();
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N * N; i++) {
		int stu_num = 0;
		int a = 0;
		int b = 0;
		int c = 0;
		int d = 0;
		cin >> stu_num >> a >> b >> c >> d;
		stu[stu_num][1] = a; stu[stu_num][2] = b; stu[stu_num][3] = c; stu[stu_num][4] = d;
		locate(stu_num);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int num = board[i][j];
			int s = 0;
			for (int k = 0; k < 4; k++) {
				int x = dx[k] + i;
				int y = dy[k] + j;

				if (board[x][y] == stu[num][1] || board[x][y] == stu[num][2] || board[x][y] == stu[num][3] || board[x][y] == stu[num][4]) s++;
			}
			
			if (s == 1) {
				ans += 1;
			}
			else if (s == 2) {
				ans += 10;
			}
			else if (s == 3) {
				ans += 100;
			}
			else if (s == 4) {
				ans += 1000;
			}
		}
	}

	cout << ans << '\n';
	return 0;
}