백준 21609) 상어 중학교(C언어)

21609번: 상어 중학교

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록

www.acmicpc.net

구현 문제 중 같은 과정을 반복해서 점수의 총합을 구하는 문제로 다소 복잡한 편입니다.

복잡한 알고리즘은 사용되지 않았지만 코드가 길고 고려해야 할 사항이 많아 자세히 설명하려 합니다.

bool type을 표현하기 위해 매크로 TRUE와 FALSE를 각각 1과 0으로 정의했습니다.

(C99 표준에는 stdbool.h 헤더파일에 bool 타입이 정의되어 있지만 매크로 사용으로 대체했습니다.)

#define TRUE (1)
#define FALSE (0)

격자에서 블록의 위치를 표현하는 자료형을 선언했습니다.

typedef struct{
	int row, col;
}pos_t;

문제에서 정의한 그룹 정보를 저장할 자료형을 선언했습니다.

std는 기준 블록의 위치입니다.

num_of_rainbow는 그룹에서 무지개 블록의 개수입니다.

blocks 배열에는 그룹에 포함된 모든 블록의 위치 정보가 저장됩니다.

num_of_blocks는 그룹에 포함된 모든 블록의 개수입니다.

typedef struct{
	pos_t std;
	int num_of_rainbow;
	pos_t blocks[400];
	int num_of_blocks;
}group_t;

전역 변수는 아래와 같습니다.

int N, M;
int grid[20][20];
int score;
group_t* groups;
int num_of_groups;
int dRow[] = { 1, -1, 0, 0 };
int dCol[] = { 0, 0, 1, -1 };

/* queue */
pos_t queue[401];
int cntQueue, idxQueue;

먼저 격자에서 group을 나누는 함수, set_groups()를 작성했습니다.

격자를 탐색하면서 일반 블록(무지개 블록 혹은 검은 블록이 아닌 블록)을 만나면 상하좌우 4방향을 탐색하여 무지개 블록이 주변에 있는지 혹은 같은 색의 일반 블록이 있는지 확인합니다.

(그룹의 조건을 만족하려면 반드시 2개 이상의 블록이 인접해야 하기 때문입니다.)

만약 그룹의 조건을 만족한다면 bfs로 다시 주변을 탐색하며 그룹에 포함할 블록들을 확인합니다.

이 때, groups는 길이가 정해지지 않은 포인터 변수이므로 메모리 동적 할당으로 새로운 group을 저장할 공간을 마련합니다. (모든 동적 할당된 메모리는 프로그램 종료 전 메모리 해제를 실시합니다.)

새로이 동적으로 할당된 group의 각 구조체 변수들을 초기화한 뒤 bfs를 실시합니다.

void set_groups(){
	int check[20][20];
	int newR, newC;
	int flag;
	group_t* group;

	memset(check, FALSE, sizeof(check));

	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++){
			if (grid[r][c] <= 0) continue;
			else if (check[r][c] == TRUE) continue;
			
			/* check 4 directions */
			flag = FALSE;
			for (int d = 0; d < 4; d++){
				newR = dRow[d] + r;
				newC = dCol[d] + c;
				if (newR < 0 || newR >= N || newC < 0 || newC >= N) continue;
				else if (grid[newR][newC] == 0) flag = TRUE;
				else if (grid[newR][newC] == grid[r][c]) flag = TRUE;
			}
			if (flag == FALSE) continue;
			
			/* add new group */
			if (num_of_groups++ == 0)
				groups = malloc(sizeof(group_t));
			else
				groups = realloc(groups, sizeof(group_t) * num_of_groups);

			group = &groups[num_of_groups - 1];
			group->std.row = r;
			group->std.col = c;
			group->num_of_blocks = 0;
			group->num_of_rainbow = 0;
			
			bfs(group, check, r, c);
		}
}

bfs를 실시하면서 group에 포함시키는 블록은 기준 블록과 같은 색이거나 무지개 블록이여야만 합니다.

이 때, 무지개 블록은 여러 group에 동시에 포함될 수 있음을 고려해야 합니다.

check 배열에는 일반 블록의 방문 여부를 저장하고 check_rainbow 배열에는 무지개 블록의 방문 여부를 저장했습니다.

C언어 표준 라이브러리에는 queue 자료구조가 없으므로 전역 변수로 선언한

pos_t queue[401], int cntQueue, idxQueue 를 이용하여 queue 자료구조를 구현했습니다.

queue에는 격자의 최대 크기(400)만큼 element가 push될 수 있으므로 배열의 최대크기를 401로 설정했습니다.

cntQueue는 queue에 push된 element의 총 개수입니다.

idxQueue는 다음에 pop하게 되는 element의 index입니다.

void bfs(group_t* group, int check[][20], int r, int c){
	int std = grid[r][c];
	int row, col;
	int newR, newC;
	int check_rainbow[20][20];

	memset(check_rainbow, FALSE, sizeof(check_rainbow));

	queue[0].row = r;
	queue[0].col = c;
	check[r][c] = TRUE;
	cntQueue = 1, idxQueue = 0;

	while (idxQueue < cntQueue){
		/* pop */
		row = queue[idxQueue].row;
		col = queue[idxQueue].col;
		idxQueue++;

		add_block_into_group(group, row, col);
		
		for (int d = 0; d < 4; d++){
			newR = row + dRow[d];
			newC = col + dCol[d];
			if (newR < 0 || newR >= N || newC < 0 || newC >= N) continue;
			else if (grid[newR][newC] == 0 && check_rainbow[newR][newC] == TRUE) continue;
			else if (check[newR][newC] == TRUE) continue;
			else if (grid[newR][newC] < 0) continue;
			else if (grid[newR][newC] > 0 && grid[newR][newC] != std) continue;

			/* push */
			queue[cntQueue].row = newR;
			queue[cntQueue].col = newC;
			cntQueue++;

			if (grid[newR][newC] != 0)
				check[newR][newC] = TRUE;
			else
				check_rainbow[newR][newC] = TRUE;
		}
	}
}

현재 격자에서 group을 모두 나눈 뒤 그 중 가장 큰 group을 찾는 로직이 필요합니다.

문제에서 정의한 로직을 그대로 구현하여 가장 적합한 group의 index를 반환하는 함수를 작성했습니다.

groups를 그 길이만큼 탐색하면서 아래의 조건을 비교합니다. 필요한 데이터는 group_t에 구조체 변수로 선언되어 있습니다.

1. 가장 크기가 큰 블록을 찾습니다. (num_of_blocks)

2. 무지개 블록의 수가 가장 많은 블록을 찾습니다. (num_of_rainbow)

3. 기준 블록의 행이 가장 큰 것을 찾습니다. (std.row)

4. 기준 블록의 열이 가장 큰 것을 찾습니다. (std.col)

group_t* get_largest_group(){
	int max_num = -1;
	int largest_group_idx = -1;

	for (int i = 0; i < num_of_groups; i++){
		if (groups[i].num_of_blocks > max_num){
			max_num = groups[i].num_of_blocks;
			largest_group_idx = i;
		}
		else if (groups[i].num_of_blocks == max_num){
			if (groups[i].num_of_rainbow > groups[largest_group_idx].num_of_rainbow){
				max_num = groups[i].num_of_blocks;
				largest_group_idx = i;
			}
			else if (groups[i].num_of_rainbow == groups[largest_group_idx].num_of_rainbow){
				if (groups[i].std.row > groups[largest_group_idx].std.row){
					max_num = groups[i].num_of_blocks;
					largest_group_idx = i;
				}
				else if (groups[i].std.row == groups[largest_group_idx].std.row && groups[i].std.col > groups[largest_group_idx].std.col){
					max_num = groups[i].num_of_blocks;
					largest_group_idx = i;
				}
			}
		}
	}
	return &groups[largest_group_idx];
}

가장 적합한 group을 전달하면 격자에서 그룹에 포함된 모든 블록들을 삭제하고

(삭제한 블록의 개수 ^ 2) 만큼 점수를 더하는 함수를 작성했습니다.

삭제된 블록은 격자에 -2로 표현했습니다.

void remove_group(group_t* group){
	pos_t pos;
	for (int i = 0; i < group->num_of_blocks; i++){
		pos = group->blocks[i];
		grid[pos.row][pos.col] = -2;
	}
	score += group->num_of_blocks * group->num_of_blocks;
}

격자에 중력이 작용하는 로직을 구현했습니다.

문제에서 정의한 중력은 일반 블록과 무지개 블록에만 영향을 준다는 점에 주의해야 합니다.

(검은 블록은 중력의 영향을 받지 않습니다.)

void activate_gravity(){
	int bottom, temp;
	for (int c = 0; c < N; c++)
		for (int r = N - 2; r >= 0; r--){
			if (grid[r][c] >= 0){
				for (bottom = r; bottom < N - 1; bottom++){
					if (grid[bottom + 1][c] != -2) break;
				}
				temp = grid[bottom][c];
				grid[bottom][c] = grid[r][c];
				grid[r][c] = temp;
			}
		}
}

격자를 반시계방향으로 회전하는 함수를 구현했습니다.

void turn_counterclockwise(){
	int temp[20][20];
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			temp[r][c] = grid[c][N - 1 - r];
	memcpy(grid, temp, sizeof(grid));
}

groups는 동적 할당된 메모리를 저장하므로 사용 후에는 반드시 메모리를 해제해야 합니다.

메모리 해제 후, groups의 길이를 저장하는 전역 변수 num_of_groups는 0으로 만들어줍니다.

void free_groups(){
	num_of_groups = 0;
	free(groups);
}

아래는 제출한 코드입니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE (1)
#define FALSE (0)

typedef struct{
	int row, col;
}pos_t;

typedef struct{
	pos_t std;
	int num_of_rainbow;
	pos_t blocks[400];
	int num_of_blocks;
}group_t;

int N, M;
int grid[20][20];
int score;
group_t* groups;
int num_of_groups;
int dRow[] = { 1, -1, 0, 0 };
int dCol[] = { 0, 0, 1, -1 };

/* queue */
pos_t queue[401];
int cntQueue, idxQueue;

void add_block_into_group(group_t* group, int row, int col){
	pos_t* pos = &(group->blocks[group->num_of_blocks]);
	pos->row = row;
	pos->col = col;
	group->num_of_blocks++;

	if (grid[row][col] == 0) group->num_of_rainbow++;
}

void bfs(group_t* group, int check[][20], int r, int c){
	int std = grid[r][c];
	int row, col;
	int newR, newC;
	int check_rainbow[20][20];

	memset(check_rainbow, FALSE, sizeof(check_rainbow));

	queue[0].row = r;
	queue[0].col = c;
	check[r][c] = TRUE;
	cntQueue = 1, idxQueue = 0;

	while (idxQueue < cntQueue){
		/* pop */
		row = queue[idxQueue].row;
		col = queue[idxQueue].col;
		idxQueue++;

		add_block_into_group(group, row, col);
		
		for (int d = 0; d < 4; d++){
			newR = row + dRow[d];
			newC = col + dCol[d];
			if (newR < 0 || newR >= N || newC < 0 || newC >= N) continue;
			else if (grid[newR][newC] == 0 && check_rainbow[newR][newC] == TRUE) continue;
			else if (check[newR][newC] == TRUE) continue;
			else if (grid[newR][newC] < 0) continue;
			else if (grid[newR][newC] > 0 && grid[newR][newC] != std) continue;

			/* push */
			queue[cntQueue].row = newR;
			queue[cntQueue].col = newC;
			cntQueue++;

			if (grid[newR][newC] != 0)
				check[newR][newC] = TRUE;
			else
				check_rainbow[newR][newC] = TRUE;
		}
	}
}

void set_groups(){
	int check[20][20];
	int newR, newC;
	int flag;
	group_t* group;

	memset(check, FALSE, sizeof(check));

	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++){
			if (grid[r][c] <= 0) continue;
			else if (check[r][c] == TRUE) continue;
			
			/* check 4 directions */
			flag = FALSE;
			for (int d = 0; d < 4; d++){
				newR = dRow[d] + r;
				newC = dCol[d] + c;
				if (newR < 0 || newR >= N || newC < 0 || newC >= N) continue;
				else if (grid[newR][newC] == 0) flag = TRUE;
				else if (grid[newR][newC] == grid[r][c]) flag = TRUE;
			}
			if (flag == FALSE) continue;
			
			/* add new group */
			if (num_of_groups++ == 0)
				groups = malloc(sizeof(group_t));
			else
				groups = realloc(groups, sizeof(group_t) * num_of_groups);

			group = &groups[num_of_groups - 1];
			group->std.row = r;
			group->std.col = c;
			group->num_of_blocks = 0;
			group->num_of_rainbow = 0;
			
			bfs(group, check, r, c);
		}
}

group_t* get_largest_group(){
	int max_num = -1;
	int largest_group_idx = -1;

	for (int i = 0; i < num_of_groups; i++){
		if (groups[i].num_of_blocks > max_num){
			max_num = groups[i].num_of_blocks;
			largest_group_idx = i;
		}
		else if (groups[i].num_of_blocks == max_num){
			if (groups[i].num_of_rainbow > groups[largest_group_idx].num_of_rainbow){
				max_num = groups[i].num_of_blocks;
				largest_group_idx = i;
			}
			else if (groups[i].num_of_rainbow == groups[largest_group_idx].num_of_rainbow){
				if (groups[i].std.row > groups[largest_group_idx].std.row){
					max_num = groups[i].num_of_blocks;
					largest_group_idx = i;
				}
				else if (groups[i].std.row == groups[largest_group_idx].std.row && groups[i].std.col > groups[largest_group_idx].std.col){
					max_num = groups[i].num_of_blocks;
					largest_group_idx = i;
				}
			}
		}
	}
	return &groups[largest_group_idx];
}

void remove_group(group_t* group){
	pos_t pos;
	for (int i = 0; i < group->num_of_blocks; i++){
		pos = group->blocks[i];
		grid[pos.row][pos.col] = -2;
	}
	score += group->num_of_blocks * group->num_of_blocks;
}

void activate_gravity(){
	int bottom, temp;
	for (int c = 0; c < N; c++)
		for (int r = N - 2; r >= 0; r--){
			if (grid[r][c] >= 0){
				for (bottom = r; bottom < N - 1; bottom++){
					if (grid[bottom + 1][c] != -2) break;
				}
				temp = grid[bottom][c];
				grid[bottom][c] = grid[r][c];
				grid[r][c] = temp;
			}
		}
}

void turn_counterclockwise(){
	int temp[20][20];
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			temp[r][c] = grid[c][N - 1 - r];
	memcpy(grid, temp, sizeof(grid));
}

void free_groups(){
	num_of_groups = 0;
	free(groups);
}

void print_grid(){
	printf("=========================\n");
	for (int r = 0; r < N; r++){
		for (int c = 0; c < N; c++){
			if (grid[r][c] == -2)
				printf("      ");
			else
				printf("%3d   ", grid[r][c]);
		}
		printf("\n");
	}
	printf("=========================\n");
}

int main(){
	group_t* group;
	
	scanf("%d %d", &N, &M);
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			scanf("%d", &grid[r][c]);

	while (TRUE){
		//print_grid();
		set_groups();
		if (num_of_groups == 0) break;
		group = get_largest_group();
		remove_group(group);
		activate_gravity();
		turn_counterclockwise();
		activate_gravity();
		free_groups();
		//printf("score = %d\n", score);
	}
	
	printf("%d", score);
	return 0;
}

질문과 코드 지적은 언제나 환영합니다 !

개발자 송씨 블로그

백준 21609) 상어 중학교(C언어)

티스토리툴바