[코드트리 45] 예술성

++22.12.12 코드 갱신해봤다

https://www.codetree.ai/frequent-problems/artistry/description

코드트리

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int N;
int board[30 + 2][30 + 2];
int num[30 + 2][30 + 2];

int g_num = 1;
int cnt;

struct _st
{
	int block_cnt;
	int real_num;
}Groups[900];


struct _qt
{
	int x, y;
};
std::queue<_qt> Q;
int visited[30 + 2][30 + 2];


int Edge[900 + 2][900 + 2];	// 맞닿아있는 변의 수 

int tmp[30 + 2][30 + 2];
int M;


// dir
int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d", &N);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &board[r][c]);
		}
	}
}

void DFS(int x, int y, int type)
{
	
	num[x][y] = g_num;

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
		if (num[nx][ny]) continue;
		if (board[nx][ny] != type) continue;
		DFS(nx, ny, type);
		cnt++;
	}

}


void get_groups() // FF + DFS
{
	// init
	memset(num, 0, sizeof(num));
	g_num = 1;
	cnt = 1;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (num[r][c]) continue;
			cnt = 1;	// 블럭 개수 세는 용도
			DFS(r, c, board[r][c]);
			Groups[g_num] = { cnt, board[r][c] };
			//printf("%d %d %d\n", g_num, cnt, board[r][c]);
			g_num++;
		}
	}
	g_num--;
}


void BFS(int x, int y, int type)
{
	// init
	Q = {};
	Q.push({ x, y });
	visited[x][y] = 1;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1)continue;
			if (num[nx][ny] != type) {
				int comp = num[nx][ny];
				Edge[type][comp]++;	// type 그룹과 comp 그룹이 맞닿아있는 변의 개수
				continue;
			}
			if (visited[nx][ny]) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
}


void get_edge()	// FF + BFS
{
	// init
	memset(visited, 0, sizeof(visited));
	memset(Edge, 0, sizeof(Edge));

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (visited[r][c]) continue;
			BFS(r, c, num[r][c]);
		}
	}
}


int get_hscore()
{
	int score = 0; 
	for (int i = 1; i <= g_num - 1; i++) {
		for (int j =  i + 1; j <= g_num; j++) {
			if (Edge[i][j] == 0) continue;
			int res = (Groups[i].block_cnt + Groups[j].block_cnt) * Groups[i].real_num * Groups[j].real_num * Edge[i][j];		
			score += res;
			//printf("%d %d\n", res, score);
		}
	}
	return score;
}


void rotate_ten()
{
	// init
	memset(tmp, 0, sizeof(tmp));
	std::queue<int> Q;
	M = N / 2;
	
	for (int r = 0; r < N; r++) Q.push(board[r][M]);
	int col = 0;
	while (!Q.empty()) {
		tmp[M][col] = Q.front();
		Q.pop();
		col++;
	}

	for (int c = N - 1; c >= 0; c--) Q.push(board[M][c]);
	int row = 0;
	while (!Q.empty()) {
		tmp[row][M] = Q.front();
		Q.pop();
		row++;
	}
	//debug(2);
}


void rotate_CW(int gx, int gy)
{
	for (int r = 0; r < M; r++) {
		for (int c = 0; c < M; c++) {
			tmp[gx + r][gy + c] = board[gx + M - 1 - c][gy + r];
		}
	}
}



void rotate_cube()
{
	rotate_CW(0, 0);
	rotate_CW(0, M + 1);
	rotate_CW(M + 1, 0);
	rotate_CW(M + 1, M + 1);

	// tmp2board
	memcpy(board, tmp, sizeof(board));
}



int simulation()
{
	int total = 0;
	for (int i = 0; i <= 3; i++) { 
		get_groups();
		get_edge();
		total += get_hscore();
		rotate_ten();
		rotate_cube();
	}
	return total;
}


int main()
{
	input();
	int ans = simulation();
	printf("%d\n", ans);
	return 0;
}

Flood Fill 한번 할 수는 없을까 하다가 그냥 2번 돌렸다. 

그룹 나누어주는 것은 DFS로 돌리고, 인접 선분의 개수 구하는 것은 BFS로 탐색했다.

 

이전에 푼 코드를 보니까 Gi, Gj 선정하는것을 조합으로(무려...ㅋㅋㅋ) 구했던데, 그렇게 하면 실행시간이 거의 40배 가까이 더 나온다. 그럴 필요 없고, 각 그룹들의 정보를 담아줄 구조체 배열(최대 30 * 30 맵이므로 각 칸마다 숫자가 다르면 그룹 수는 900개 까지 나올 수 있음) 을 선언하고 루프 2번 돌려주면서 예술점수 구하면 된다.

 

십자모양 회전도 인덱싱으로 하고 싶었는데, 문제 푸는 중에는 못찾고 그냥 큐 써서 넣었다 뺐다. 

해설 코드 보니까 아래와 같이 구현하면 큐를 쓰지 않아도 돼서 시간 좀 더 줄일 수 있을 것 같다.

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            // Case 2 - 1. 세로줄에 대해서는 (i, j) -> (j, i)가 됩니다.
            if(j == n / 2)
                next_arr[j][i] = arr[i][j];
            // Case 2 - 2. 가로줄에 대해서는 (i, j) -> (n - j - 1, i)가 됩니다.
            else if(i == n / 2)
                next_arr[n - j - 1][i] = arr[i][j];
        }
}

대신 정사각형 모양 회전은 최근에 공부한 인덱싱 사용해서 풀었다. 이 부분도 실행 시간 감소에 한 몫 한듯 싶다.