[코드트리] 이상한 다트 게임 (삼성 SW 역량테스트 2019 하반기 오후 1번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/odd-dart-game

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

 

이상한 다트 게임 문제 풀이는 BOJ 17822 : 원판 돌리기와 같다.

단, 평균에 대한 처리가 다르다. (코드트리는 평균을 구할 때, 소숫점 아래의 수를 버린다.)

void averageCircle()
{
	...
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (circle[r][c] == 0) continue;

			if (circle[r][c] < avg) circle[r][c]++;
			// else if (circle[r][c] == avg && remain != 0) circle[r][c]++;
			else if (circle[r][c] > avg) circle[r][c]--;
		}
	}
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (50 + 5)

int T;
int N, M, Q;

int circle[MAX][MAX];

int X[MAX];
int D[MAX];
int K[MAX];

typedef struct st
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX * MAX];
int wp, rp;

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

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

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

	for (int i = 1; i <= Q; i++)
		scanf("%d %d %d", &X[i], &D[i], &K[i]);
}

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", circle[r][c]);
		putchar('\n');
	}
}

void rotate(int x, int d, int k)
{
	int tmp[MAX] = { 0 };

	if (d == 1) k = M - k; /* 반시계 방향 k칸은 시계 방향으로 M - k 칸 */

	for (int r = x; r <= N; r += x)
	{
		for (int c = 1; c <= M - k; c++) tmp[c + k] = circle[r][c];
		for (int c = M - k + 1; c <= M; c++) tmp[c - (M - k)] = circle[r][c];
		for (int c = 1; c <= M; c++) circle[r][c] = tmp[c];
	}
}

int BFS(int r, int c, int visit[][MAX])
{
	int flag = 0;

	wp = rp = 0;

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

	visit[r][c] = 1;

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

		if (out.c == 1)
		{
			if (circle[out.r][M] == circle[r][c] && visit[out.r][M] == 0)
			{
				queue[wp].r = out.r;
				queue[wp++].c = M;

				visit[out.r][M] = 1;

				flag = 1;
			}
		}
		else if (out.c == M)
		{
			if (circle[out.r][1] == circle[r][c] && visit[out.r][1] == 0)
			{
				queue[wp].r = out.r;
				queue[wp++].c = 1;

				visit[out.r][1] = 1;

				flag = 1;
			}
		}

		for (int k = 0; k < 4; k++)
		{
			int nr, nc;

			nr = out.r + dr[k];
			nc = out.c + dc[k];

			if (circle[nr][nc] == 0) continue;

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

				visit[nr][nc] = 1;

				flag = 1;
			}
		}
	}

	return flag;
}

void deleteCircle(int visit[][MAX])
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (visit[r][c]) circle[r][c] = 0;
}

void averageCircle()
{
	int sum, cnt, avg, remain;

	sum = cnt = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (circle[r][c]) sum += circle[r][c], cnt++;

	if (cnt == 0) return;

	avg = sum / cnt;
	remain = sum % cnt;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (circle[r][c] == 0) continue;

			if (circle[r][c] < avg) circle[r][c]++;
			// else if (circle[r][c] == avg && remain != 0) circle[r][c]++;
			else if (circle[r][c] > avg) circle[r][c]--;
		}
	}
}

void allBFS()
{
	int visit[MAX][MAX] = { 0 };

	int deleteflag = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (circle[r][c] != 0 && visit[r][c] == 0)
			{
				int tmp = BFS(r, c, visit);

				if (tmp)
				{
					deleteCircle(visit);
					deleteflag = 1;
				}
				else
					visit[r][c] = 0;
			}
		}
	}

	if (deleteflag == 0) averageCircle();
}

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

		for (int q = 1; q <= Q; q++)
		{
			rotate(X[q], D[q], K[q]);
			allBFS();
		}

		int sum = 0;
		for (int i = 1; i <= N; i++)
			for (int c = 1; c <= M; c++)
				sum += circle[i][c];

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

	return 0;
}