[코드트리] 색깔 폭탄 (삼성 SW 역량테스트 2021 상반기 오전 2번)

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

 

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

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

 

색깔 폭탄 문제 풀이는 BOJ 21609 : 상어 중학교와 비슷하지만, 우선순위가 다르다.

상어 중학교는 (1) 빨간색 폭탄이 많고, (3) 동일 조건 내 열이 가장 큰 칸을 찾아야 한다. 

색깔 폭탄은 빨간색 폭탄이 적어야 하고, 동일 조건 내 열이 가장 작은 칸을 선택하면 된다.

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (20 + 5)

#define RED (0)
#define BLACK (-1)
#define EMPTY (-2)

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

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

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

typedef struct st2
{
	int total;
	int normal;
	int red;
	int maxR;
	int minC;
}BLOCK_INFO;

void input()
{
	scanf("%d %d\n", &N, &M);
	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = BLACK;

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

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == EMPTY) printf("   ");
			else printf("%2d ", MAP[r][c]);
		}
		putchar('\n');
	}
	putchar('\n');
}

void rotate(int MAP[MAX][MAX])
{
	int tmpMAP[MAX][MAX] = { 0 };

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

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			MAP[r][c] = tmpMAP[c][N - r + 1];
}

void blockDownColumn(int map[MAX][MAX], int col)
{
	for (int r = N; r >= 1; r--)
	{
		if (map[r][col] == BLACK || map[r][col] == EMPTY) continue;

		int start_row = r;
		while (1)
		{
			if (map[start_row + 1][col] != EMPTY) break;

			if (map[start_row + 1][col] == EMPTY)
			{
				int tmp = map[start_row][col];
				map[start_row][col] = map[start_row + 1][col];
				map[start_row + 1][col] = tmp;
			}

			start_row++;
		}
	}
}

void blockDown(int map[MAX][MAX])
{
	for (int col = 1; col <= N; col++) blockDownColumn(map, col);
}

BLOCK_INFO BFS(int r, int c, int visit[MAX][MAX], int map[MAX][MAX])
{
	BLOCK_INFO blockInfo = { 0 };
	RC queue[MAX * MAX] = { 0 };
	int rp, wp, block;

	blockInfo.normal++; /* 최소 하나의 블럭이 존재 */
	blockInfo.maxR = r;
	blockInfo.minC = c;

	rp = wp = 0;

	block = map[r][c];

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

	visit[r][c] = 1;

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

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

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

			if (map[nr][nc] == BLACK || visit[nr][nc] == 1) continue;

			if (map[nr][nc] == block || map[nr][nc] == RED)
			{
				visit[nr][nc] = 1;

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

				if (map[nr][nc] == RED) blockInfo.red++;
				else blockInfo.normal++;

				if (map[nr][nc] == block)
				{
					if ((nr > blockInfo.maxR)
						|| (nr == blockInfo.maxR && nc < blockInfo.minC))
					{
						blockInfo.maxR = nr;
						blockInfo.minC = nc;
					}
				}
			}

		}
	}

	blockInfo.total = blockInfo.normal + blockInfo.red;

	return blockInfo;
}

void deleteBlock(int r, int c, int visit[MAX][MAX], int map[MAX][MAX])
{
	RC queue[MAX * MAX] = { 0 };
	int rp, wp, block;

	rp = wp = 0;

	block = map[r][c];
	map[r][c] = EMPTY;

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

	visit[r][c] = 1;

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

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

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

			if (map[nr][nc] == BLACK || visit[nr][nc] == 1) continue;

			if (map[nr][nc] == block || map[nr][nc] == RED)
			{
				visit[nr][nc] = 1;

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

				map[nr][nc] = EMPTY;
			}
		}
	}
}

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

		int ans = 0;

		while (1)
		{
			int maxBlock, minRed, maxr, minc;

			minRed = 0x7fff0000;
			maxBlock = maxr = minc = -1;
			for (int r = 1; r <= N; r++)
			{
				for (int c = 1; c <= N; c++)
				{
					if (MAP[r][c] == BLACK || MAP[r][c] == RED || MAP[r][c] == EMPTY) continue;

					int visit[MAX][MAX] = { 0 }; /* 매번 초기화 해야 한다. */
					BLOCK_INFO tmp = BFS(r, c, visit, MAP);
					
					if (tmp.total <= 1) continue;

					/* 크기가 가장 큰 블록의 판단 */
					if ((maxBlock < tmp.total)
						|| (maxBlock == tmp.total && minRed > tmp.red)
						|| (maxBlock == tmp.total && minRed == tmp.red && maxr < tmp.maxR)
						|| (maxBlock == tmp.total && minRed == tmp.red && maxr == tmp.maxR && minc >tmp.minC))
					{
						maxBlock = tmp.total;
						minRed = tmp.red;
						maxr = tmp.maxR;
						minc = tmp.minC;
					}
				}
			}

			if (maxBlock == -1) break;

			ans += (maxBlock * maxBlock);
			
			int visit[MAX][MAX] = { 0 };
			deleteBlock(maxr, minc, visit, MAP);

			blockDown(MAP);
			rotate(MAP);
			blockDown(MAP);
		}

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

	return 0;
}