백준 21608 - 상어 초등학교(C++)

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

21608번: 상어 초등학교

삼성SW 역량 테스트 문제였습니다.

정렬 기준을 만들어 정렬하면 쉽게 풀 수 있는 문제였습니다.

문제 조건

출력 예시

채우는 과정을 예시 입력 1번을 통해 확인하겠습니다.

1. 4번이 채워질때, 좋아하는 학생이 인접한 칸이 없음으로, 빈칸이 가장 많은 가운데에 놓아진다.

2. 3번이 채워질때, 좋아하는 학생이 있고(4번), 해당 자리들의 빈칸 수가 모두 같음으로, 행이 가장 작은 곳에 앉는다.

3. 9번이 채워질때, 좋아하는 학생이 있고(3번), 해당 자리들의 빈칸 수, 행이 모두 같음으로, 가장 작은 열에 앉는다.

4. 8번이 채워질때, 좋아하는 학생이 있음으로(3,9,4번) 가장 근접한 자리에 앉는다.

-> 해당 방식으로 자리를 순서대로 채워나갑니다.

 

1. 빈칸 앉기

typedef struct st {
	int many;
	int empty;
	int x;
	int y;
}st;

void fill_map(int x) {
	vector<st> can;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] == 0) {
				st now = { 0,0,i,j };
				for (int k = 0; k < 4; k++) {
					int xx = i + dx[k];
					int yy = j + dy[k];
					if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
						if (map[xx][yy] == 0) now.empty++;
						else if (map[xx][yy] != 0) {
							for (int w = 0; w < student[x].size(); w++) {
								if (map[xx][yy] == student[x][w]) {
									now.many++;
									break;
								}
							}
						}
					}
				}
				can.push_back(now);
			}
		}
	}
	sort(can.begin(), can.end(), cmp);
	map[can[0].x][can[0].y] = x;
}

구조체 st에는 좋아하는 학생 수, 빈칸 수, 행, 열을 저장할 수 있습니다.

이중 for문을 통해 먼저 앉을 수 있는 자리를 찾습니다. 

앉을 수 있는 자리를 찾았다면, 해당 위치에서 4방향 탐색을 통해서 좋아하는 학생수, 빈칸 수를 얻습니다.

-> 이를 vector can에 저장했습니다.

 

vector can을 정렬 기준에 따라 정렬한 뒤, 가장 좋은 자리에 X번을 앉게 합니다.

 

 

2. 정렬 기준 세우기

bool cmp(st a, st b) {
	if (a.many > b.many) return true;
	else if (a.many == b.many) {
		if (a.empty > b.empty) return true;
		else if (a.empty == b.empty) {
			if (a.x < b.x) return true;
			else if (a.x == b.x) {
				if (a.y < b.y) return true;
				else return false;
			}
			else return false;
		}
		else return false;
	}
	else return false;
}

1. 좋아하는 학생이 많은 순서

2. 빈칸이 많은 순서

3. 행이 가장 작은 순서

4. 열이 가장 작은 순서

-> 해당 순서대로 정렬을 하면 됩니다.

 

 

문제 접근 방법

1. X번 학생이 좋아하는 학생 번호를 저장한다.

2. 순서대로 학생을 채운다.

   2-1. X번 학생이 앉을 수 있는 곳을 모두 찾는다.

   2-2. 앉을 수 있는 곳을 정렬 기준에 따라 정렬한다.

3. 학생이 모두 앉았다면, 행복도를 찾는다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N, ans;
int map[21][21];
int order[401];
vector<int> student[401];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
typedef struct st {
	int many;
	int empty;
	int x;
	int y;
}st;

bool cmp(st a, st b) {
	if (a.many > b.many) return true;
	else if (a.many == b.many) {
		if (a.empty > b.empty) return true;
		else if (a.empty == b.empty) {
			if (a.x < b.x) return true;
			else if (a.x == b.x) {
				if (a.y < b.y) return true;
				else return false;
			}
			else return false;
		}
		else return false;
	}
	else return false;
}

void fill_map(int x) {
	vector<st> can;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] == 0) {
				st now = { 0,0,i,j };
				for (int k = 0; k < 4; k++) {
					int xx = i + dx[k];
					int yy = j + dy[k];
					if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
						if (map[xx][yy] == 0) now.empty++;
						else if (map[xx][yy] != 0) {
							for (int w = 0; w < student[x].size(); w++) {
								if (map[xx][yy] == student[x][w]) {
									now.many++;
									break;
								}
							}
						}
					}
				}
				can.push_back(now);
			}
		}
	}
	sort(can.begin(), can.end(), cmp);
	map[can[0].x][can[0].y] = x;
}

void Find_happy() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int x = map[i][j];
			int happy = 0;
			for (int k = 0; k < 4; k++) {
				int xx = i + dx[k];
				int yy = j + dy[k];
				if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
					for (int w = 0; w < student[x].size(); w++) {
						if (student[x][w] == map[xx][yy]) {
							happy++;
							break;
						}
					}
				}
			}
			ans += pow(10, happy - 1);
		}
	}
}

void solve() {
	for (int i = 0; i < pow(N, 2); i++) {
		fill_map(order[i]);
	}
	Find_happy();
	cout << ans << "\n";
}

int arr[101][101], M;

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0; i < pow(N, 2); i++) {
		int x;
		cin >> x;
		for (int j = 0; j < 4; j++) {
			int y;
			cin >> y;
			student[x].push_back(y);
		}
		order[i] = x;
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!