백준 21608 상어 초등학교

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

 

- 빡구현 문제이다. 시간복잡도는 N^2명의 학생이 N^2개의 칸을 순회하면서 자신이 앉을 위치를 찾아나가므로 총 O(N^4)이다.

 

- 일단 student_order배열에 앉을 순서대로 학생들의 번호를 넣고, 학생들을 배치하기 시작한다. 이 과정에서 모든 칸을 순회하면서, 어느 칸에서 좋아하는 학생이 인접 칸에 가장 많이 있는지를 탐색한다. 이 과정에서 벡터에 후보 칸을 모두 담는데, 현재까지 인접 칸의 좋아하는 학생의 최대 수를 계속해서 갱신한다. 갱신 과정은

 

 

  1. 인접 칸의 좋아하는 학생 수 최대 > 현재 칸의 인접 칸의 좋아하는 학생 수 : 후보군이 될 수 없으므로 continue

  2. 인접 칸의 좋아하는 학생 수 최대 == 현재 칸의 인접 칸의 좋아하는 학생 수 : 후보군이 되므로 push_back

  3. 인접 칸의 좋아하는 학생 수 최대 < 현재 칸의 인접 칸의 좋아하는 학생 수 : 벡터를 clear해서 비워주고, 현재 칸을 후보군에 넣는다.

 

- 이 과정을 마치고, vector size가 1이면 해당 학생을 그 칸에 앉히고, 만약 여러 후보가 존재하는 경우 2번 조건인 인접한 칸 중 빈 칸이 가장 많은 자리를 구한다. 이 과정은 위와 동일하게 전개를 해 주면 된다. 

 

- 이 후에도 만약 후보군이 여러 개 존재한다면, sort 메서드를 사용하되 customazing한 compare함수를 넣어 주어서 행이 가장 작은 => 열이 가장 작은 최종 후보를 선택한다.

 

- 문제는 40분만에 풀었지만, 디버깅하는데 거의 30분을 써버렸다. 이유는 for문이 여러 개가 중첩되다보니 j,k를 i,j로 쓰는 실수를 하여 out of bounds 에러가 떴다. ㅠㅠ

 

- 작년 상반기인가 기출문제인데, 합격 컷이 빠르게 제출한 1솔~2솔이라고 한다. 1시간내로 제출을 한다면 충분히 합격권이 가능한 것 같다. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
int map[21][21];
int student_order[401];
int student[401][4];
int n;
void debugging() {
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++) {
			cout << map[j][k] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}
bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first) {
		return a.second < b.second;
	}
	return a.first < b.first;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n * n; i++) {
		int num; cin >> num;
		student_order[i] = num;
		for (int j = 0; j < 4; j++) {
			cin >> student[num][j];
		}
	}
	for (int i = 1; i <= n*n; i++) {
		int now_student = student_order[i];
		vector<pair<int, int>> area;
		int friend_num = 0;
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (map[j][k]) continue;
				int temp_friend_num = 0;
				for (int l = 0; l < 4; l++) {
					int nx = j + dx[l]; int ny = k + dy[l];
					if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
					if (!map[nx][ny]) continue;
					for (int m = 0; m < 4; m++) {
						if (map[nx][ny] == student[now_student][m]) {
							temp_friend_num++; break;
						}
					}
				}
				if (friend_num > temp_friend_num) continue;
				else if (friend_num == temp_friend_num) area.push_back({ j,k });
				else {
					area.clear();
					friend_num = temp_friend_num;
					area.push_back({ j,k });
				}
			}
		}

		if (area.size() > 1) {
			vector<pair<int, int>> area2;
			int max_blank_num = 0;
			for (int j = 0; j < area.size(); j++) {
				int x = area[j].first; int y = area[j].second;
				int temp_blank_num = 0;
				for (int k = 0; k < 4; k++) {
					int nx = x + dx[k]; int ny = y + dy[k];
					if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
					if (!map[nx][ny]) temp_blank_num++;
				}
				if (max_blank_num > temp_blank_num) continue;
				else if (max_blank_num == temp_blank_num) area2.push_back({ x,y });
				else {
					area2.clear();
					max_blank_num = temp_blank_num;
					area2.push_back({ x,y });
				}
			}
			sort(area2.begin(), area2.end(), compare);
			int answer_x = area2[0].first; int answer_y = area2[0].second;
			map[answer_x][answer_y] = now_student;

		}
		else {
			int answer_x = area[0].first; int answer_y = area[0].second;
			map[answer_x][answer_y] = now_student;
		}
	}
	int answer = 0;
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++) {
			int now_student = map[j][k];
			int friend_num = 0;
			for (int l = 0; l < 4; l++) {
				int nx = j + dx[l]; int ny = k + dy[l];
				if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
				if (!map[nx][ny]) continue;
				for (int m = 0; m < 4; m++) {
					if (map[nx][ny] == student[now_student][m]) {
						friend_num++; break;
					}
				}
			}
			answer += (pow(10, friend_num) / 10);
		}
	}
	cout << answer;
}