알고리즘/[ADV] 삼성 SW 역량 테스트 A형

[코드트리] 예술성 (삼성 SW 역량테스트 2022 상반기 오전 2번)

피로물든딸기 2024. 6. 10. 21:09
반응형

삼성 A형 전체 링크

 

참고

- BOJ 2667 : 단지번호붙이기

- N x N 2차원 배열 뒤집기, 회전하기

 

https://www.codetree.ai/training-field/frequent-problems/problems/artistry

이후 설명 및 입/출력은 링크 참고

 

그룹을 나눈 후, 그룹을 이루는 숫자, 그룹에 속한 칸의 수, 그룹의 번호를 구분하기 하기 위한 구조체를 만든다.

typedef struct st1
{
	int value;
	int count;	
	int groupNumber;
}GROUP;

 

그룹을 구분할 때, 2차원 좌표를 탐색하기 위한 구조체와 좌표 배열을 선언한다.

typedef struct st2
{
	int r;
	int c;
}RC;

int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

 

input은 2차원 배열을 잘 받아오면 된다.

#define MAX (29 + 5)

int N;
int MAP[MAX][MAX];

void input()
{
	scanf("%d", &N);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

그룹 구분하기

 

visit 배열을 만들어서, BFS로 그룹을 구분한다.

BFS 내부에서 visit 배열을 방문할 때, 해당 groupNumber를 적는다.

BFS가 종료되면 groupNumber를 증가하여 각 그룹을 구분하게 된다.

	for (int round = 0; round < 4; round++)
	{
		int visit[MAX][MAX] = { 0 }; // visit 이면서 stamp로 사용
		GROUP group[MAX * MAX] = { 0 };
		int gcnt = 0;

		int groupNumber = 1;
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (visit[r][c] != 0) continue;
				
				GROUP ret = BFS(r, c, visit, groupNumber);
				group[gcnt++] = ret;
				groupNumber++;
			}
		}

		// ...
	}

 

visit에 그룹 번호를 남기게 되면 최종 결과는 아래와 같다.

 

BOJ 2667 : 단지번호붙이기를 참고하여 BFS를 구현한다.

(r, c) 의 값과 인접한 값(MAP[nr][nc] == value)을 찾아서 visit에 번호를 남긴다.

groupNumber, MAP[r][c]에 실제 값과 개수를 GROUP 구조체에 저장하여 return한다.

GROUP BFS(int r, int c, int visit[MAX][MAX], int groupNumber)
{
	GROUP ret = { 0 };
	RC queue[MAX * MAX] = { 0 };
	int wp, rp, count, value;

	wp = rp = 0;

	count = 1;
	value = MAP[r][c];

	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = groupNumber;

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (visit[nr][nc] == 0 && MAP[nr][nc] == value)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = groupNumber;
				count++;
			}
		}
	}

	ret.value = value;
	ret.count = count;
	ret.groupNumber = groupNumber;

	return ret;
}

조화로움 구현

 

조화로움은 맞닿아 있는 변의 수로 정의된다.

visit에서 그룹을 구분하였으므로, visit을 모두 순회하면서 상하좌우 다른 값이 있는 경우, harmony 배열에 count 한다.

이때, 그룹은 N * N개가 존재할 수 있으므로 harmony의 배열은 [MAX * MAX][MAX * MAX]가 된다.

그리고 서로 인접한 값이 각각 count 되기 때문에 실제 값을 2로 나누어야 한다.

int harmony[MAX * MAX][MAX * MAX];

void makeHormony(int visit[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			for (int d = 0; d < 4; d++)
			{
				int nr, nc;

				nr = r + dr[d];
				nc = c + dc[d];
				
				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

				if (visit[r][c] == visit[nr][nc]) continue;
								
				harmony[visit[r][c]][visit[nr][nc]]++;
				harmony[visit[nr][nc]][visit[r][c]]++;
			}
		}
	}

	for (int r = 1; r <= N * N; r++)
		for (int c = 1; c <= N * N; c++)
			harmony[r][c] /= 2;
}

 

harmony를 구했으므로, GROUP을 모두 비교하면서 점수를 계산하면 된다.

int getScore(GROUP group[], int gcnt)
{
	int score = 0;
	for (int i = 0; i < gcnt - 1; i++)
	{
		for (int k = i + 1; k < gcnt; k++)
		{
			GROUP a = group[i];
			GROUP b = group[k];

			score 
				+= (a.count + b.count) * a.value * b.value * harmony[a.groupNumber][b.groupNumber];
		}
	}

	return score;
}

 

그리고 harmony를 계산하기 전에 초기화하는 것을 잊지 말자.

	for (int r = 1; r <= N * N; r++)
		for (int c = 1; c <= N * N; c++)
			harmony[r][c] = 0;

배열의 회전

 

N x N 2차원 배열 뒤집기, 회전하기를 참고하자.

십자 회전은 temp1에 map을 복사, temp2를 90도 반시계 회전, temp2의 십자가 값만 map에 복사하면 된다.

void rotateCenter(int map[MAX][MAX])
{
	int temp1[MAX][MAX] = { 0 };
	int temp2[MAX][MAX] = { 0 };

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			temp1[r][c] = map[r][c];

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			temp2[r][c] = temp1[c][N + 1 - r];

	for (int r = 1; r <= N; r++)
		map[r][N / 2 + 1] = temp2[r][N / 2 + 1];

	for (int c = 1; c <= N; c++)
		map[N / 2 + 1][c] = temp2[N / 2 + 1][c];
}

 

시계방향 rotate는 특정 좌표를 기준으로 rotate 하는 함수를 만들면 된다.

void rotate(int map[MAX][MAX], int sr, int sc)
{
	int size = N / 2;
	int temp[MAX][MAX] = { 0 };

	for (int r = 0; r < size; r++)	
		for (int c = 0; c < size; c++)		
			temp[r][c] = map[r + sr][c + sc];

	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			map[r + sr][c + sc] = temp[size - c - 1][r];
}

 

해당 좌표가 4개이므로, 좌표를 나눠서 4번 호출하면 된다.

	rotate(MAP, 1, 1);
	rotate(MAP, 1 + N / 2 + 1, 1);
	rotate(MAP, 1, 1 + N / 2 + 1);
	rotate(MAP, 1 + N / 2 + 1, 1 + N / 2 + 1);

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (29 + 5)

int T;
int N;
int MAP[MAX][MAX];

typedef struct st1
{
	int value;
	int count;	
	int groupNumber;
}GROUP;

typedef struct st2
{
	int r;
	int c;
}RC;

int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int harmony[MAX * MAX][MAX * MAX];

void printMap(int map[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%2d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void input()
{
	scanf("%d", &N);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

GROUP BFS(int r, int c, int visit[MAX][MAX], int groupNumber)
{
	GROUP ret = { 0 };
	RC queue[MAX * MAX] = { 0 };
	int wp, rp, count, value;

	wp = rp = 0;

	count = 1;
	value = MAP[r][c];

	queue[wp].r = r;
	queue[wp++].c = c;

	visit[r][c] = groupNumber;

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (visit[nr][nc] == 0 && MAP[nr][nc] == value)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				visit[nr][nc] = groupNumber;
				count++;
			}
		}
	}

	ret.value = value;
	ret.count = count;
	ret.groupNumber = groupNumber;

	return ret;
}

void makeHormony(int visit[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			for (int d = 0; d < 4; d++)
			{
				int nr, nc;

				nr = r + dr[d];
				nc = c + dc[d];
				
				if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

				if (visit[r][c] == visit[nr][nc]) continue;
								
				harmony[visit[r][c]][visit[nr][nc]]++;
				harmony[visit[nr][nc]][visit[r][c]]++;
			}
		}
	}

	for (int r = 1; r <= N * N; r++)
		for (int c = 1; c <= N * N; c++)
			harmony[r][c] /= 2;
}

int getScore(GROUP group[], int gcnt)
{
	int score = 0;
	for (int i = 0; i < gcnt - 1; i++)
	{
		for (int k = i + 1; k < gcnt; k++)
		{
			GROUP a = group[i];
			GROUP b = group[k];

			score 
				+= (a.count + b.count) * a.value * b.value * harmony[a.groupNumber][b.groupNumber];
		}
	}

	return score;
}

void rotateCenter(int map[MAX][MAX])
{
	int temp1[MAX][MAX] = { 0 };
	int temp2[MAX][MAX] = { 0 };

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			temp1[r][c] = map[r][c];

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			temp2[r][c] = temp1[c][N + 1 - r];

	for (int r = 1; r <= N; r++)
		map[r][N / 2 + 1] = temp2[r][N / 2 + 1];

	for (int c = 1; c <= N; c++)
		map[N / 2 + 1][c] = temp2[N / 2 + 1][c];
}

void rotate(int map[MAX][MAX], int sr, int sc)
{
	int size = N / 2;
	int temp[MAX][MAX] = { 0 };

	for (int r = 0; r < size; r++)	
		for (int c = 0; c < size; c++)		
			temp[r][c] = map[r + sr][c + sc];

	for (int r = 0; r < size; r++)
		for (int c = 0; c < size; c++)
			map[r + sr][c + sc] = temp[size - c - 1][r];
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		int totalScore = 0;
		for (int round = 0; round < 4; round++)
		{
			int visit[MAX][MAX] = { 0 }; // visit 이면서 stamp로 사용
			GROUP group[MAX * MAX] = { 0 };
			int gcnt = 0;

			int groupNumber = 1;
			for (int r = 1; r <= N; r++)
			{
				for (int c = 1; c <= N; c++)
				{
					if (visit[r][c] != 0) continue;
				
					GROUP ret = BFS(r, c, visit, groupNumber);
					group[gcnt++] = ret;
					groupNumber++;
				}
			}

			for (int r = 1; r <= N * N; r++)
				for (int c = 1; c <= N * N; c++)
					harmony[r][c] = 0;
					
			makeHormony(visit);
			
			totalScore += getScore(group, gcnt);

			rotateCenter(MAP);
			rotate(MAP, 1, 1);
			rotate(MAP, 1 + N / 2 + 1, 1);
			rotate(MAP, 1, 1 + N / 2 + 1);
			rotate(MAP, 1 + N / 2 + 1, 1 + N / 2 + 1);
		}

		printf("%d\n", totalScore);
	}

	return 0;
}
반응형