(c++)백준 21608번: 상어 초등학교

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

21608번: 상어 초등학교

[풀이]

|r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다. => 어떤 칸의 상하좌우에 있는 칸이 인접한 칸이다.

학생의 번호와 그 학생이 좋아하는 학생들의 번호를 저장하는 struct 자료구조를 만들어 입력을 받아 순서대로 어디에 자리를 배치할지 탐색한다.

빈칸들마다 주변에 좋아하는 학생 수, 빈칸 수를 저장하여 조건에 맞게 정렬한다. 정렬했을 때 제일 앞에 있는 좌표에 해당 학생을 배치시킨다.

모든 학생을 배치시키고 각 학생의 주변 학생을 확인한  다음 만족도의 총 합을 구한다.

 

[코드]

#include <iostream>
#include <algorithm>//sort
#include <vector>
#include <map>
#include <cmath>//pow
using namespace std;

struct Stu {
	int num;//학생 번호
	int favorite[4];//좋아하는 4명
};

struct Loc {
	int x, y;//좌표
	int fav;//인접한 칸에 좋아하는 학생 수
	int blank;//인접한 비어있는 칸 수
};

bool sortLoc(Loc &A, Loc &B) {
	//좋아하는 학생 수가 같으면
	if (A.fav == B.fav) {
		//빈칸 개수가 같으면
		if (A.blank == B.blank) {
			//행이 같으면
			if (A.x == B.x) {
				//열이 작은 칸
				return A.y < B.y;
			}
			//행이 작은 칸
			else
				return A.x < B.x;
		}
		//빈칸 개수가 많은 칸
		return A.blank > B.blank;
	}
	//좋아하는 학생 수가 많은 칸
	return A.fav > B.fav;
}

int N;
int Map[21][21] = {0,};
Stu student[400];
vector<Loc>Class;
bool filled[21][21] = { false, };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
map<int, int>m;

//학생 배치하기
void Place(int num, int favorite[4]) {
	Class.clear();
	//자리 차있으면 pass
	//각각 빈칸의 인접한 칸에 좋아하는 학생 몇명인지, 빈칸 몇개인지 세기
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Map[i][j] != 0)
				continue;
			int fav_cnt = 0;
			int blank_cnt = 0;
			for (int d = 0; d < 4; d++) {
				int nx = i + dx[d];
				int ny = j + dy[d];
				//범위 확인
				if (nx <= 0 || nx > N || ny <= 0 || ny > N)
					continue;
				//빈칸이면
				if (Map[nx][ny] == 0)
					blank_cnt++;
				//아니면 좋아하는 학생인지 확인
				else {
					for (int n = 0; n < 4; n++) {
						if (Map[nx][ny] == favorite[n]) {
							fav_cnt++;
							break;
						}
					}
				}
			}
			Class.push_back({ i,j,fav_cnt,blank_cnt });
		}
	}
	sort(Class.begin(), Class.end(), sortLoc);
	int x = Class[0].x;
	int y = Class[0].y;
	Map[x][y] = num;
	return;
}

int main() {
	cin >> N;
	int num;
	int fav[4];
	for (int i = 0; i < N*N; i++) {
		cin >> student[i].num;
		//배열 student의 몇 번째 칸에 num의 좋아하는 학생 배열 있는지 저장
		m.insert(make_pair(student[i].num, i));
		for (int j = 0; j < 4; j++) {
			cin >> student[i].favorite[j];
		}
	}
	for (int i = 0; i < N*N; i++) {
		Place(student[i].num,student[i].favorite);
	}
	int answer = 0;
	//만족도 구하기
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int num = Map[i][j];
			int fav_cnt = 0;
			for (int d = 0; d < 4; d++) {
				int nx = i + dx[d];
				int ny = j + dy[d];
				if (nx <= 0 || nx > N || ny <= 0 || ny > N)
					continue;
				for (int n = 0; n < 4; n++) {
					if (Map[nx][ny] == student[m[num]].favorite[n]) {
						fav_cnt++;
						break;
					}
				}
			}
			if (fav_cnt == 0)
				continue;
			answer += pow(10, fav_cnt - 1);
		}
	}
	cout << answer << '\n';
	return 0;
}