코드트리 예술성 (C++)

문제를 그대로 구현하면 됩니다. 회전하는 부분이 있어 코드가 좀 더럽습니다. 예술성을 계산하는 부분에서는 맞닿아 있는 변의 수를 체크하기 위해 map 자료구조를 사용했습니다. 아래 방향과 오른쪽 방향만 체크하여 중복되지 않게 작성했습니다.

 

	#include <bits/stdc++.h>
	#define endl '\n'
	#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll, ll> pll;
	typedef tuple<int,int,int> tiii;
	const int INF=1e9+1;
	int dx[]={1,0,-1,0};
	int dy[]={0,1,0,-1};
	bool allchecked(vector<vector<int>>& group) {
	// 격자가 모두 그룹화가 되었는지 리턴
	int n=group.size();
	for(int i=0;i<n;i++) {
	for(int j=0;j<n;j++) {
	if(!group[i][j]) return false;
	}
	}
	return true;
	}
	vector<vector<int>> grouping(vector<vector<int>>& board) {
	// 격자를 그룹화하는 함수
	int n=board.size();
	vector<vector<int>> temp(n, vector<int>(n)), visit(n, vector<int>(n));
	int ids=0;
	while(!allchecked(temp)) {
	for(int i=0;i<n;i++) {
	for(int j=0;j<n;j++) {
	if(!temp[i][j]) {
	ids++;
	temp[i][j]=ids;
	int target=board[i][j];
	queue<pii> q;
	q.push({i,j});
	visit[i][j]=1;
	while(!q.empty()) {
	int x=q.front().first, y=q.front().second;
	q.pop();
	for(int k=0;k<4;k++) {
	int nx=x+dx[k], ny=y+dy[k];
	if(nx>=0 && nx<n && ny>=0 && ny<n) {
	if(!visit[nx][ny] && board[nx][ny]==target) {
	temp[nx][ny]=ids;
	q.push({nx,ny});
	visit[nx][ny]=1;
	}
	}
	}
	}
	}
	}
	}
	}
	return temp;
	}
	int max_index(vector<vector<int>>& group) {
	// 그룹 번호의 최댓값 리턴
	int idx=0;
	for(int i=0;i<group.size();i++) {
	for(int j=0;j<group[i].size();j++) idx=max(idx,group[i][j]);
	}
	return idx;
	}
	int score(vector<vector<int>>& board) {
	// 예술성을 계산하는 함수
	vector<vector<int>> group=grouping(board);
	int n=board.size();
	int ids=max_index(group);
	vector<vector<int>> v(ids+1, vector<int>(2)); // (그룹에 속한 칸의 수, 그룹을 이루고 있는 숫자 값)
	for(int i=0;i<n;i++) {
	for(int j=0;j<n;j++) v[group[i][j]][0]++, v[group[i][j]][1]=board[i][j];
	}
	map<pii,int> m; // ({그룹 a, 그룹 b}, 맞닿아 있는 변의 수)
	int nx, ny;
	// 아래 방향과 오른쪽 방향만 체크하여 중복되지 않게 한다
	for(int i=0;i<n;i++) {
	for(int j=0;j<n;j++) {
	// down
	nx=i+1, ny=j;
	if(nx<n && group[i][j]!=group[nx][ny]) {
	if(group[i][j]>group[nx][ny]) m[{group[nx][ny],group[i][j]}]++;
	else m[{group[i][j],group[nx][ny]}]++;
	}
	// right
	nx=i, ny=j+1;
	if(ny<n && group[i][j]!=group[nx][ny]) {
	if(group[i][j]>group[nx][ny]) m[{group[nx][ny],group[i][j]}]++;
	else m[{group[i][j],group[nx][ny]}]++;
	}
	}
	}
	// 스코어 계산
	int ret=0;
	for(auto it : m) {
	ret+=(v[it.first.first][0]+v[it.first.second][0])*v[it.first.first][1]*v[it.first.second][1]*it.second;
	}
	return ret;
	}
	vector<vector<int>> clockwise(vector<vector<int>>& field) {
	// field를 시계방향으로 회전하는 함수
	int n=field.size();
	vector<vector<int>> temp(n, vector<int>(n));
	for(int i=0;i<n;i++) {
	for(int j=0;j<n;j++) temp[j][n-i-1]=field[i][j];
	}
	return temp;
	}
	void rotate(vector<vector<int>>& board) {
	// 회전시키는 함수
	int n=board.size(), mid=board.size()/2;
	// cross
	vector<int> v;
	for(int i=0;i<mid;i++) v.push_back(board[i][mid]);
	for(int i=0;i<mid;i++) board[i][mid]=board[mid][n-1-i];
	for(int j=n-1;j>mid;j--) board[mid][j]=board[j][mid];
	for(int i=n-1;i>mid;i--) board[i][mid]=board[mid][n-1-i];
	for(int j=0;j<mid;j++) board[mid][j]=v[j];
	// 4 fields
	vector<vector<int>> field(mid, vector<int>(mid)), temp(mid, vector<int>(mid));
	// (0,0)
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) field[i][j]=board[i][j];
	temp=clockwise(field);
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) board[i][j]=temp[i][j];
	// (0, mid+1)
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) field[i][j]=board[i][j+mid+1];
	temp=clockwise(field);
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) board[i][j+mid+1]=temp[i][j];
	// (mid+1, 0)
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) field[i][j]=board[i+mid+1][j];
	temp=clockwise(field);
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) board[i+mid+1][j]=temp[i][j];
	// (mid+1, mid+1)
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) field[i][j]=board[i+mid+1][j+mid+1];
	temp=clockwise(field);
	for(int i=0;i<mid;i++) for(int j=0;j<mid;j++) board[i+mid+1][j+mid+1]=temp[i][j];
	}
	int main() {
	fastio
	//freopen("input.txt","r",stdin);
	int n; cin>>n;
	vector<vector<int>> board(n, vector<int>(n));
	for(int i=0;i<n;i++) {
	for(int j=0;j<n;j++) cin>>board[i][j];
	}
	int t=3;
	int scores=score(board);
	while(t--) {
	rotate(board);
	scores+=score(board);
	}
	cout<<scores;
	return 0;
	}

view raw codetree_art.cpp hosted with ❤ by GitHub