HERSTORY

[C++ 알고리즘] 백준 21608번 : 상어 초등학교

  • 2021년 04월 29일


Implementation

상어 초등학교

풀이과정

우선순위큐를 이용해서 구현하였다.

  1. 순서대로 학생의 자리 정하기
  2. 만족도 구하기 를 구현만 해주면 끝난다!

가장 핵심적인 부분은 우선순위큐를 작성하는 부분인 것 같다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

위의 요구대로 아래와 같이 코드를 작성했다.

// blankCnt : 비어있는 칸의 개수
// friendCnt : 인접한 칸에 있는 좋아하는 학생의 수
struct info {
	int x, y, blankCnt=0, friendCnt = 0;
	bool operator <(const info& i) const {
		if (friendCnt == i.friendCnt) {
			if (blankCnt == i.blankCnt) {
				if (x == i.x) return y > i.y;
				else return x > i.x;
			}
			else return blankCnt < i.blankCnt;
		}
		else return friendCnt < i.friendCnt;
	}
};

로 비교함수를 만들었고, 전체 자리를 우선순위큐priority_queue<info> pQ에 넣어 준 후 우선순위 큐의 top에 있는 자리에 학생을 배치해주면 끝이다.


코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct info {
	int x, y, blankCnt=0, friendCnt = 0;
	bool operator <(const info& i) const {
		if (friendCnt == i.friendCnt) {
			if (blankCnt == i.blankCnt) {
				if (x == i.x) return y > i.y;
				else return x > i.x;
			}
			else return blankCnt < i.blankCnt;
		}
		else return friendCnt < i.friendCnt;
	}
};

struct student {
	int id;
	int love[4];
	int x, y;
};

int manjok[] = { 0,1,10,100,1000 };

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

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

	// 0. 입력
	int N;
	int board[20][20] = {0,};

	cin >> N;

	vector<student> students(N * N);
	for (int i = 0; i < N * N; i++) {
		cin >> students[i].id;
		for (int j = 0; j < 4; j++) {
			cin >> students[i].love[j];
		}
	}

	// 1. 자리 배치하기
	for (int s = 0; s < N * N; s++) {
		priority_queue<info> pQ;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] == 0) {
					int blankCnt = 0, friendCnt = 0;
					for (int d = 0; d < 4; d++) {
						int nx = i + dx[d];
						int ny = j + dy[d];

						if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1) continue;
						if (board[nx][ny] == 0) blankCnt++;
						else {
							for (int k = 0; k < 4; k++) {
								if (board[nx][ny] == students[s].love[k]) {
									friendCnt++;
									break;
								}
							}
						}
					}
					pQ.push({ i,j,blankCnt , friendCnt });
				}
			}
		}

		if (!pQ.empty()) {
			int x = pQ.top().x;
			int y = pQ.top().y;

			board[x][y] = students[s].id;
			students[s].x = x;
			students[s].y = y;
		}
	}

	// 2. 만족도 계산
	int res = 0;
	for (int s = 0; s < N * N; s++) {
		int x = students[s].x;
		int y = students[s].y;

		int friends = 0;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1) continue;
			for (int k = 0; k < 4; k++) {
				if (board[nx][ny] == students[s].love[k]) {
					friends++;
					break;
				}
			}
		}
		res += manjok[friends];
	}

	cout << res;

	return 0;
}

결과

image



검색