37. [백준 21608번 / C++] 상어 초등학교

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

21608번: 상어 초등학교

 

앗, 상어잖아?! 하지만 이름만 상어고 쉬운 문제입니다.

 

문제 조건은 정말 간단합니다. 한마디로 최대한 모두가 행복할 수 있게 학생들의 자리를 배치해주는 것!

 

이때 중요한 우선순위는 문제에 정의되어 있습니다.

 

아하, 그렇다면 n x n의 각 자리에 대해서 k번호 학생에 대한 우선순위를 매기면 되겠구나!

 

라는 생각으로 저는 풀었습니다. 범위도 n <= 20이기 때문에 완전 탐색이 가능하겠죠?

 

우선순위를 매기려면 각 자리에 대해서 문제의 우선순위 조건 변수를 저장할 필요가 있습니다. 저는 이걸 구조체 struct로 y, x, love, emp 4개의 변수를 정의해서 풀었습니다.

 

바로 코드를 볼게요.

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, a[404][404], b, c, d, e, f, ret;
vector<int> adj[404], seq;
struct B{
	int y, x, love, emp;
};
vector<B> v;

struct cmp{
	bool operator()(B a, B b){
		if(a.love == b.love){
			if(a.emp == b.emp){
				if(a.y == b.y) return a.x < b.x;
				else return a.y < b.y;
			}else return a.emp > b.emp;
		}else return a.love > b.love;
	} 
};

void solve(int k){
	v.clear();
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(a[i][j] != 0) continue;
			int love = 0, emp = 0;
			for(int h = 0; h < 4; h++){
				int ny = i + dy[h];
				int nx = j + dx[h];
				if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
				if(a[ny][nx] == 0) emp++;
				for(int p : adj[k]){
					if(p == a[ny][nx]) love++;
				}
			}
			v.push_back({i, j, love, emp});
		}
	}
	
	sort(v.begin(), v.end(), cmp());
	a[v[0].y][v[0].x] = k;
}
int main(){
	cin >> n;
	for(int i = 0; i < n * n; i++){
		cin >> b >> c >> d >> e >> f;
		adj[b].push_back(c);
		adj[b].push_back(d);
		adj[b].push_back(e);
		adj[b].push_back(f);
		seq.push_back(b);
	}
	for(int i : seq){
		solve(i);
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			int love = 0;
			for(int h = 0; h < 4; h++){
				int ny = i + dy[h];
				int nx = j + dx[h];
				if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
				for(int p : adj[a[i][j]]){
					if(p == a[ny][nx]) love++;
				}
			}
			if(love == 1) ret += 1;
			else if(love == 2) ret += 10;
			else if(love == 3) ret += 100;
			else if(love == 4) ret += 1000;
		}
	}
	cout << ret << "\n";
}

 

struct B가 보이시나요? 그리고 이에 대한 vector<B> v도 보이실거예요.

 

이제 solve함수를 보면, n x n의 모든 자리를 탐색하면서 그 자리의 주위에 빈칸인 자리는 몇 개인지 또, 좋아하는 학생은 몇 명인지 체크해서 모두 vector<B> v에 push_back합니다!

 

이제 sort를 해주면되는데 이 sort의 기준은 struct cmp에 정의되어 있습니다. 한 번 보시면 아실거예요. 참고로

bool cmp(B a, B b){
//... 같은 내용
}

 

이런식으로 struct cmp가 아닌 bool cmp의 함수로 그냥 선언하면 에러가 나더라고요... 왠지는 저도 잘 모르겠습니다. 아마 내부에서 돌아갈 때 (이하 생략) 어쨌든 그렇습니다. 필요하다고 생각하시는 분은 암기하셔서 사용하시는 것도 좋을 것 같습니다.

 

어찌되었든 이제 모든 학생들의 자리 배치가 끝나고 각 자리에 대해서 점수를 매기면 이 문제의 끝입니다.

 

삼성이 서류가 합격했다면 좋았을텐데 말이죠... 다음 기회에는 직접 현장에서 풀 수 있다면 좋겠네요