BOJ 21608.상어 초등학교

참고자료

얍문's Coding World..
구현 방식을 복잡하게 생각해서 잘 떠오르지 않았는데 도움이 많이 됐다!

꿀팁

• 자리를 구하기 위해 필요한 인자가 무엇인지 정리해보자

구현방식

1) 자리 지정 함수: set_seat

1. 전체 자리를 탐색한다

• 비어있지 않다면, 다음 자리 탐색
• 비어있다면, 인접한 자리 탐색

  • 인접한 자리가 비어있을 경우, empty인자+=1
  • 인접한 자리가 비어있지 않을 경우, 현재 학생의 친구와 비교

    인접한 자리에 좋아하는 친구가 있을 경우, friend인자+=1

2. 1 과정을 통해 얻은 자리 정보를 조건에 맞추어 정렬
   : compare 함수 참고

2) 만족도 계산 함수: cal_satisfaction

1. 전체 자리를 탐색한다.
2. 해당 자리에 앉은 학생의 친한친구가 인접한 자리에 있는지 확인
3. 있다면 ++friend_tmp;
4. 각 자리마다 만족도 result에 계산

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 20

using namespace std;

int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

struct STUDENT {
	int num = 0;
	int Friend[4];
};

int Friend[MAX*MAX][4];
vector<STUDENT> vec_std;

struct POS {
	int Friend;
	int Empty;
	int r;
	int c;
};

int SEAT[MAX][MAX];

bool  compare(POS p1, POS p2) {
	if (p1.Friend > p2.Friend)
		return true;
	else if (p1.Friend == p2.Friend) {
		if (p1.Empty > p2.Empty)
			return true;
		else if (p1.Empty == p2.Empty) {
			if (p1.r > p2.r)
				return true;
			else if (p1.r == p2.r) {
				if (p1.c > p2.c)
					return true;
				else
					return false;
			}
			else return false;
		}
		else
			return false;
	}
	else
		return false;
}

void set_seat(int std_num, int N) {
	int r, c, i, j;
	int nr, nc;
	int Empty_tmp, Friend_tmp;
	vector<POS> SEAT_INFO;

	for (r = 0; r < N; r++) {
		for (c = 0; c < N; c++) {
			if (SEAT[r][c] != 0)
				continue;

			Empty_tmp = 0, Friend_tmp = 0;

			for (i = 0; i < 4; i++) {
				nr = r + dr[i];
				nc = c + dc[i];

				if (nr <0 || nr>=N || nc<0 || nc>=N)
					continue;

				if (SEAT[nr][nc] == 0)
					++Empty_tmp;
				else {
					for (j = 0; j < 4; j++) {
						if (SEAT[nr][nc] == Friend[std_num - 1][j])
							++Friend_tmp;
					}
				}
			}
			SEAT_INFO.push_back({ Friend_tmp, Empty_tmp, r, c });
		}
	}
	sort(SEAT_INFO.begin(), SEAT_INFO.end(), compare);
	SEAT[SEAT_INFO[0].r][SEAT_INFO[0].c] = std_num;	
}

int cal_satisfaction(int N) {
	int r, c, i, j;
	int nr, nc;
	int Friend_tmp;
	int result = 0;

	for (r = 0; r < N; r++) {
		for (c = 0; c < N; c++) {
			Friend_tmp = 0;
			for (i = 0; i < 4; i++) {
				nr = r + dr[i];
				nc = c + dc[i];
				if (nr <0 || nr>=N || nc<0 || nc>=N)
					continue;

				for (j = 0; j < 4; j++) {
					if (Friend[SEAT[r][c] - 1][j] == SEAT[nr][nc])
						++Friend_tmp;
				}
			}
			if (Friend_tmp == 1)
				result += 1;
			else if (Friend_tmp == 2)
				result += 10;
			else if (Friend_tmp == 3)
				result += 100;
			else if (Friend_tmp == 4)
				result += 1000;
		}
	}
	return result;
}

int main(void) { 
	int N;
	int input[5];
	int i, j, k;

	//INPUT
	scanf("%d", &N);
	for (i = 0; i < N*N; i++) {
		scanf("%d %d %d %d %d", input, input + 1, input + 2, input + 3, input + 4);
		vec_std.push_back({ input[0], {input[1], input[2], input[3], input[4]} });
		Friend[input[0] - 1][0] = input[1];
		Friend[input[0] - 1][1] = input[2];
		Friend[input[0] - 1][2] = input[3];
		Friend[input[0] - 1][3] = input[4];
	}

	//Set seat
	for (i = 0; i < vec_std.size(); i++)
		set_seat(vec_std[i].num, N);

	printf("%d\n", cal_satisfaction(N));
}