백준 21608번 상어 초등학교

문제 링크입니다: www.acmicpc.net/problem/21608

21608번: 상어 초등학교

단순 구현 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 각 학생마다 좋아하는 학생들이 4명이 있으므로 해당 정보를 map 자료구조로 저장합니다. (likeFriends)

2. 입력받은 학생 순서로 자리를 배치하는데 문제에서 주어진 규칙대로 배치를 진행하면 됩니다.

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

3. 만족도를 구해줍니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <map>
	using namespace std;
	const int MAX = 20;
	const int FRIENDS_MAX = 4;
	const int INF = 400 + 40;
	typedef struct
	{
	int y, x;
	} Coord;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[MAX] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
	int N;
	int classRoom[MAX][MAX];
	map<int, vector<int>> likeFriends;
	bool doesContainLikeFriend(vector<int> friendList, int adjacentStudent)
	{
	for (int i = 0; i < FRIENDS_MAX; i++)
	{
	if (friendList[i] == adjacentStudent)
	{
	return true;
	}
	}
	return false;
	}
	void placeStudent(int student)
	{
	int likeFriendCnt = 0;
	int adjacentEmptySeatCnt = 0;
	Coord coord = { INF, INF };
	for (int y = 0; y < N; y++)
	{
	for (int x = 0; x < N; x++)
	{
	if (classRoom[y][x])
	{
	continue;
	}
	int tempLikeFriendCnt = 0;
	int tempAdjacentEmptySeatCnt = 0;
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
	{
	continue;
	}
	int adjacentStudent = classRoom[nextY][nextX];
	// 옆자리가 빈자리
	if (adjacentStudent == 0)
	{
	tempAdjacentEmptySeatCnt++;
	continue;
	}
	// 옆자리가 좋아하는 친구
	if (doesContainLikeFriend(likeFriends[student], adjacentStudent))
	{
	tempLikeFriendCnt++;
	}
	}
	// 첫 번째 조건: 좋아하는 학생이 인접한 칸에 가장 많은 칸
	if (tempLikeFriendCnt > likeFriendCnt)
	{
	likeFriendCnt = tempLikeFriendCnt;
	adjacentEmptySeatCnt = tempAdjacentEmptySeatCnt;
	coord = { y, x };
	continue;
	}
	// 두 번째 조건: 인접한 칸 중에서 비어있는 칸이 가장 많은 칸
	if (likeFriendCnt == tempLikeFriendCnt)
	{
	if (tempAdjacentEmptySeatCnt > adjacentEmptySeatCnt)
	{
	adjacentEmptySeatCnt = tempAdjacentEmptySeatCnt;
	coord = { y, x };
	continue;
	}
	// 세 번째 조건: 행의 번호가 가장 작은 칸, 행이 동일할 경우 열의 번호가 가장 작은 칸
	if (adjacentEmptySeatCnt == tempAdjacentEmptySeatCnt)
	{
	if (coord.y > y || (coord.y == y && coord.x > x))
	{
	coord = { y, x };
	}
	}
	}
	}
	}
	classRoom[coord.y][coord.x] = student;
	}
	int calculateSatisfaction(void)
	{
	int satisfaction = 0;
	for (int y = 0; y < N; y++)
	{
	for (int x = 0; x < N; x++)
	{
	int student = classRoom[y][x];
	vector<int> friends = likeFriends[student];
	int likeFriendCnt = 0;
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
	{
	continue;
	}
	int adjacentStudent = classRoom[nextY][nextX];
	for (int likeFriend : friends)
	{
	if (likeFriend == adjacentStudent)
	{
	likeFriendCnt++;
	break;
	}
	}
	}
	switch (likeFriendCnt)
	{
	case 0:
	break;
	case 1:
	satisfaction += 1;
	break;
	case 2:
	satisfaction += 10;
	break;
	case 3:
	satisfaction += 100;
	break;
	case 4:
	satisfaction += 1000;
	break;
	}
	}
	}
	return satisfaction;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	vector<int> students(N*N);
	for (int i = 0; i < N*N; i++)
	{
	cin >> students[i];
	vector<int> friends(FRIENDS_MAX);
	for (int j = 0; j < FRIENDS_MAX; j++)
	{
	cin >> friends[j];
	}
	likeFriends[students[i]] = friends;
	}
	for (int i = 0; i < N*N; i++)
	{
	placeStudent(students[i]);
	}
	int result = calculateSatisfaction();
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~