BOJ 17822 : 원판 돌리기 (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

www.acmicpc.net/workbook/view/1152 (A형 문제집)

www.acmicpc.net/problem/17822

원판이지만 2차원 배열에서 같은 번호면 큐에 넣어서 BFS 탐색을 하면 된다.

circle[r][c] = 0인 경우는 탐색하지 않으므로, 주변을 0으로 만들고, (1, 1)부터 input을 받는다.

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

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

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

이제 원판을 돌리는 함수를 구현해보자.

반시계 방향으로 1칸 움직이는 것은 시계 방향으로 M - 1칸 움직이는 것과 동일하므로,

시계 방향만 구해주면 된다.

따라서 d == 1 (반시계)인 경우는 k = M - k로 변경한다.

이제 아래와 같이 M = 6, k = 2인 원판을 돌려보자. (시계 방향으로 2칸 돌려보자.)

편의상 배열은 1부터 시작한다.

c = 1부터 c = M - k 까지는 배열이 초과하지 않으므로, 그대로 tmp[c + k]부터 복사한다.

남은 5, 6은 tmp의 index가 1부터 시작하도록 작업하면 된다.

마지막으로 임시 배열 tmp를 circle에 다시 복사하면 된다. rotate를 참고하자.

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];
	}
}

rotate가 끝나면, 같은 숫자를 지운다.

지울 숫자가 없다면, 남은 숫자의 평균을 보고 원판의 숫자를 변경한다.

따라서 ALLBFS는 아래와 같이 구현된다.

void ALLBFS()
{
	int visit[MAX][MAX] = { 0 };
	
	int deleteflag = 0; /* 지워졌는지 check 하는 flag */
	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; /* 모든 (r, c)에 대해 한 번이라도 지워졌다면 1 */
				}
				else 
					visit[r][c] = 0;
			}
		}
	}

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

먼저 circle의 모든 (r, c)를 돌면서 (r, c)의 주변의 값이 같은지 찾는다.(BFS)

BFS는 1개라도 지울 숫자가 있다면 1을, 없다면 0을 return한다. 지울 숫자는 visit에 check한다.

지울 숫자가 있다면, deleteCircle에서 visit을 보고 0으로 만든다.

지울 숫자가 없다면, visit[r][c] = 0으로 다시 복구한다.

모든 (r, c)에 대해 지울 숫자가 없었다면(deleteFlag == 0) averageCircle로 평균값을 계산하여 circle을 갱신한다.

BFS는 4방향 탐색을 하지만, 원형이므로,

column이 1인 경우는 column이 M일 때 탐색하고, column이 M인 경우는 1일 때 탐색하는 코드를 추가한다.

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

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) /* 원형이므로 1인 경우는 M을 확인 */
		{
			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) /* M인 경우는 1을 확인 */
		{
			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;
}

한 번이라도 추가로 queue에 들어온다면, 지울 숫자가 있다는 뜻이므로 flag = 1로 만든다.

deleteCircle은 visit을 보고 circle을 0으로 만든다.

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;
}

averageCircle은 아래와 같이 구현된다.

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]--;
		}
	}	
}

먼저 모든 원판이 지워진 경우가 있을 수 있으므로, 모든 circle이 0 (cnt == 0)인 경우는 return한다.

문제의 조건에서 average보다 작은 경우만 circle의 숫자를 증가시키므로,

나머지도 고려해서 circle의 값을 수정해야한다.

만약 남은 숫자가 6개이고 총 합이 22라면,

22 / 6 = 3.xxx 이므로 나머지가 0이 아니다. 따라서 이 경우는 circle[r][c] == 3인 경우도 증가시켜야한다.

남은 숫자가 6이고, 총 합이 18이라면,

18 / 6 = 3이고 나머지가 0이므로 변경이 없어야 한다.

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (50 + 5)

int N, M, T;

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;

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

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

	for (int i = 1; i <= T; 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 dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };

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)
{
	input();

	for (int t = 1; t <= T; t++)
	{
		rotate(X[t], D[t], K[t]);
		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;
}

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 20061 : 모노미노도미노 2 (삼성 SW TEST A형) (0)	2021.03.31
BOJ 17825 : 주사위 윷놀이 (삼성 SW TEST A형) (0)	2021.03.28
BOJ 17837 : 새로운 게임 2 (삼성 SW TEST A형) (0)	2021.03.23
BOJ 17779 : 게리맨더링 2 (삼성 SW TEST A형) (0)	2021.03.20
BOJ 17142 : 연구소 3 (삼성 SW TEST A형) (0)	2021.03.17

피로물든딸기의 라이브러리

BOJ 17822 : 원판 돌리기 (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 17822 : 원판 돌리기 (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바