백준 21608 - 상어 초등학교

문제링크

• 백준 21608

문제설명

• N x N 크기의 격자 형태의 교실이 있다. 교실은 (1,1) 부터 시작해서 (N,N) 까지의 좌표를 갖는다.
• 학교에 다니는 학생 수는 총 N^2 명으로 교실 각 칸에 자리를 배정받는다.
• 각 학생은 4명의 좋아하는 학생이 있다.
• 자리를 정하는 학생 순서대로 학생의 번호와 해당 학생이 좋아하는 학생 4명의 번호가 주어진다.
• 자리를 정하는 기준은 다음과 같다.
  • 비어있는 각 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
  • 위 조건을 만족하는 칸이 여러 개라면 인접한 칸 중에서 비어있는 칸이 가장 많은 칸을 자리로 정한다.
  • 위 조건을 만족하는 칸도 여러 개인 경우 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개인 경우 열의 번호가 가장 작은 칸으로 자리를 정한다.
• 학생의 만족도 조사는 자리를 모두 정한 후 계산할 수 있다.
  • 각 학생이 인접한 칸에 앉은 좋아하는 학생의 수에 따라 다음과 같이 만족도가 결정된다.
  • 인접한 칸에 좋아하는 학생이 0명이 경우: 0
  • 인접한 칸에 좋아하는 학생이 1명이 경우: 1
  • 인접한 칸에 좋아하는 학생이 2명이 경우: 10
  • 인접한 칸에 좋아하는 학생이 3명이 경우: 100
  • 인접한 칸에 좋아하는 학생이 4명이 경우: 1000
• 학생의 만족도의 총합을 출력하라

문제접근

• 만족도 조사를 위해 각 학생이 좋아하는 학생들의 데이터를 배열 studentLikeInfo[401][4] 에 담아둔다.
• 앉을 수 있는 빈칸 중에서 학생의 조건에 맞는 후보 자리 조사를 해야한다.
• 앉을 자리 후보 데이터를 관리하기 위해 구조체를 다음과 같이 정의한다.
  • xpos, ypos, likes, empty
  • x좌표, y좌표, 인접한 자리에 좋아하는 학생의 수, 인접한 자리에 빈칸의 수
• 자리를 정하는 학생 순서대로 빈칸을 탐색한 후 해당 빈칸에서 인접한 자리의 정보를 조사한다.
• 모든 빈칸에 대한 탐색이 끝나면 자리를 정하는 기준에 따라 정렬한다.
• 정렬된 데이터의 가장 앞에 해당하는 데이터의 자리가 해당 학생의 최종 자리가 된다.
• 자리 배치를 완료하고 위 과정을 전체 학생에 대해 반복한다.

구현

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

typedef struct _data {
	int xpos, ypos, likes, empty;
} Data;

int N;
int studentLikeInfo[401][4];
int board[21][21];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<Data> cand;

bool cmp(Data d1, Data d2) {
	if (d1.likes != d2.likes) {
		return d1.likes > d2.likes;
	}
	else if (d1.empty != d2.empty) {
		return d1.empty > d2.empty;
	}
	else if (d1.xpos != d2.xpos) {
		return d1.xpos < d2.xpos;
	}
	else {
		return d1.ypos < d2.ypos;
	}
}

void setData(int num, int x, int y) {
	Data idata = { x, y, 0, 0 };
	for (int dir = 0; dir < 4; dir++) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (nx<1 || nx>N || ny<1 || ny>N) continue;
		for (int i = 0; i < 4; i++) {
			if (studentLikeInfo[num][i] == board[nx][ny]) {
				idata.likes++;
			}
		}
		if (board[nx][ny] == 0) idata.empty++;
	}
	cand.push_back(idata);
}

int getScore(int x, int y) {
	int num = board[x][y];
	int cnt = 0;
	for (int dir = 0; dir < 4; dir++) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (nx<1 || nx>N || ny<1 || ny>N) continue;
		for (int i = 0; i < 4; i++) {
			if (board[nx][ny] == studentLikeInfo[num][i]) cnt++;
		}
	}
	if (cnt == 0) return 0;
	else if (cnt == 1) return 1;
	else if (cnt == 2) return 10;
	else if (cnt == 3) return 100;
	else if (cnt == 4) return 1000;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	memset(board, 0, sizeof(board));
	scanf("%d", &N);
	int num, s1, s2, s3, s4;
	for (int i = 0; i < N*N; i++) {
		scanf("%d %d %d %d %d", &num, &s1, &s2, &s3, &s4);
		studentLikeInfo[num][0] = s1;
		studentLikeInfo[num][1] = s2;
		studentLikeInfo[num][2] = s3;
		studentLikeInfo[num][3] = s4;

		cand.clear();
		// find empty space
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				if (board[r][c] == 0) {
					setData(num, r, c);
				}
			}
		}
		sort(cand.begin(), cand.end(), cmp);
		board[cand[0].xpos][cand[0].ypos] = num;
	}
	// printBoard();

	// 만족도 조사
	int answer = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			answer += getScore(r, c);
		}
	}
	printf("%d\n", answer);
	return 0;
}