[BOJ 21608] 상어 초등학교 (C++)

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

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

int classroom[21][21] = { 0, };

struct info {
	int like, vacant, row, col;
	bool operator<(const info &b) const {
		if (like == b.like) {
			if (vacant == b.vacant) {
				if (row == b.row) {
					return col > b.col;		//열 오름차순으로
				}
				return row > b.row;			//행 오름차순으로
			}
			return vacant < b.vacant;
		}
		return like < b.like;			//like 내림차순으로
	}
};


int main() {
	int N, num, x;
	int ans = 0;
	vector<int> order;
	map<int, vector<int> > m;
	cin >> N;
	for (int i = 0; i < N * N; i++) {
		cin >> num;
		order.push_back(num);
		for (int j = 0; j < 4; j++) {
			cin >> x;
			m[num].push_back(x);
		}
	}
	for (int student : order) {
		priority_queue<info> q;
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				if (classroom[r][c] != 0)
					continue;
				int l = 0; int v = 0;
				for (int d = 0; d < 4; d++) {
					int nr = r + dx[d];
					int nc = c + dy[d];
					if (nr >= 1 && nr <= N && nc >= 1 && nc <= N) {
						if (classroom[nr][nc] == 0)
							v++;
						else {
							if (find(m[student].begin(), m[student].end(), classroom[nr][nc]) != m[student].end())
								l++;
						}
					}
				}
				q.push({ l,v,r,c });
			}
		}
		info i = q.top();
		classroom[i.row][i.col] = student;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int student = classroom[i][j];
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int nr = i + dx[k];
				int nc = j + dy[k];
				if (nr >= 1 && nr <= N && nc >= 1 && nc <= N) {
					if (find(m[student].begin(), m[student].end(), classroom[nr][nc]) != m[student].end()) {
						cnt++;
					}
				}
			}
			switch (cnt) {
			case 0:
				break;
			case 1:
				ans += 1;
				break;
			case 2:
				ans += 10;
				break;
			case 3:
				ans += 100;
				break;
			case 4:
				ans += 1000;
				break;
			}
		}
	}
	
	cout << ans << "\n";
	return 0;

}

구현 문제.

 

우선순위 큐를 이용해서, 조건을 만족하는 것이 제일 front에 나오도록 했다.

(like 내림차순->vacant 내림차순->행 오름차순->열 오름차순)

 

탐색은 N*N의 자리를 돌면서(이때 자리가 정해진 좌표는 탐색하지 않는다), 주변 4방향의 상태를 체크한 후(빈칸인지, 좋아하는 학생 수), 우선순위 큐에 {좋아하는 학생 수, 빈칸, 행, 열} 을 넣어준다. (행,열)의 인접에 좋아하는 학생 수와 빈칸이 몇개 있는지 기록하는 것이다. N*N개 탐색이 끝나면, 큐의 제일 맨 앞쪽에 있는 것이 적정 좌석이다. 

그곳에 해당 student를 배정해주면 된다.

 

struct를 만들어서 like, vacant, row, col 을 멤버로 두었다. 해당 (row, col) 좌표 인접에 like가 몇개인지 vacant 가 몇개인지 나타내는 것이다. 비교 연산자를 오버로딩해서, priority_queue를 쓸 때 조건에 맞게 정렬이 가능하도록 했다.