BOJ 21609 : 상어 중학교 (삼성 SW TEST A형)

 

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

 

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/21609

 

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

 

무지개 블록, 검은색 블록, 그리고 빈칸을 define하자.

보통 배열의 빈칸은 0을 쓰지만, 여기에서는 무지개 블록이 존재하므로 -2로 define한다.

 

좌표를 저장하기 위한 RC 구조체와 블록 그룹의 우선순위를 결정할 BLOCK_INFO 구조체를 만든다.

 

그리고 MAP 주변을 검은색 블록으로 벽을 만들고, (1, 1)부터 입력을 받도록 하자.

#define MAX (20 + 5)

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

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

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

typedef struct st2
{
	int normal;
	int rainbow;
	int minR;
	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]);
}

---

구현할 사항이 많기 때문에 쉬운 것 부터 구현해보자.

 

배열을 90도 반시계 방향으로 돌려야 한다.

회전한 배열의 (1, 1)은 원래 배열의 (1, 3)이다.

회전한 배열의 (1, 2)은 원래 배열의 (2, 3)이다.

회전한 배열의 (1, 3)은 원래 배열의 (3, 3)이다.

 

→ (1, column)의 값은 (column, N - 1 + 1)

 

(2, 1)의 값은 (3, 2)로 간다.

...

 

→ (row, column)의 값은 (column, N - row + 1)

 

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

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

---

중력의 구현, 즉 배열을 아래로 밀어 넣는 것은 column 하나에 대해 구현한다.

 

먼저 가장 row가 큰 것, 즉 가장 아래의 블록부터 아래로 내린다.

BLACK은 움직이지 않고, EMPTY는 블록이 아니므로 무시한다.

블록이 선택되면 row + 1을 check하여 EMPTY가 될 때까지 아래로 내린다.

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

 

모든 column에 대해 blockDownColumn을 실행하면 배열에 중력이 작용하게 된다.

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

---

가장 큰 블록 그룹을 찾는 것은 단지번호붙이기와 유사하게 BFS를 이용해 주변 4방향 탐색을 한다.

 

현재 좌표 (r, c)를 기준으로 블록 그룹을 4방향 탐색한다.

BLOCK_INFO의 normal에는 전체 블록의 개수를 저장하고, rainbow에는 RAINBOW 블록의 개수를 저장한다.

그리고 minR, minC를 매번 갱신해둔다. (기준 블록의 행이 가장 작고, 열의 번호가 가장 작아야 한다.)

 

4방향 탐색할 때, map[r][c]의 블록과 같거나 RAINBOW 블록만 queue에 담는다.

그리고 RAINBOW인 경우는 rainbow 개수를 증가시킨다.

그리고 현재 저장된 좌표를 비교하여 row가 더 작거나 row가 같을 때, column이 더 작으면 갱신한다.

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

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.minR = 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] == RAINBOW)
			{
				visit[nr][nc] = 1;

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

				if (map[nr][nc] == RAINBOW) blockInfo.rainbow++;

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

		}
	}

	return blockInfo;
}

 

위의 BFS는 main에서 아래와 같이 실행하게 된다.

이때, visit 배열을 매번 초기화할 필요가 있다는 것에 주의하자.

 

[..., 3, 0, 2, ...]의 배열을 예로 들 수 있다.

3과 0이 블록 그룹을 이루고 0을 visit check하면, 2의 블록이 0을 queue에 담을 수 없게 된다.

queue에 담기지 않았으므로, 3의 블록 그룹이 더 큰지, 2의 블록 그룹이 더 큰지 알 수 없게 된다.

따라서 매번 visit을 초기화하고 BFS에 넘긴다.

int maxBlock, maxRainbow, maxr, maxc;

maxBlock = maxRainbow = maxr = maxc = -1;
for (int r = 1; r <= N; r++)
{
	for (int c = 1; c <= N; c++)
	{
		if (MAP[r][c] == BLACK || MAP[r][c] == RAINBOW || MAP[r][c] == EMPTY) continue;

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

		if (tmp.normal <= 1) continue;

		/* 크기가 가장 큰 블록의 판단 */
		if ((maxBlock < tmp.normal)
			|| (maxBlock == tmp.normal && maxRainbow < tmp.rainbow)
			|| (maxBlock == tmp.normal && maxRainbow == tmp.rainbow && tmp.minR > maxr)
			|| (maxBlock == tmp.normal && maxRainbow == tmp.rainbow && tmp.minR == maxr && tmp.minC > maxc))
		{
			maxBlock = tmp.normal;
			maxRainbow = tmp.rainbow;
			maxr = tmp.minR;
			maxc = tmp.minC;
		}
	}
}

이때, 블록 그룹의 크기가 2 이상이어야 하므로 크기가 1 이하인 경우는 무시한다.

그리고 return된 BLOCK_INFO를 이용하여 아래의 우선순위대로 갱신하면 된다.

---

모든 BFS 탐색이 끝났다면 map에서 블록 그룹을 지운다.

block을 지우는 것은 위의 BLOCK_INFO에서 갱신된 maxr, maxc를 이용한다.

BFS 탐색은 위와 같고, 가능한 BLOCK에 EMPTY (-2)를 MAP에 표시만 하면 된다.  (구현은 최종 코드를 참고하자)

 

또한 maxBlock이 갱신되지 않았다면 게임을 종료하라고 하였으므로 break로 while문을 빠져나간다.

 

블록을 지울 수 있는 경우에는 지우고 난 후, ans에 점수를 추가한다.

그리고 blockDown과 rotate함수를 문제에서 제시한 대로 실행한다.

	while (1)
	{
		int maxBlock, maxRainbow, maxr, maxc;

		maxBlock = maxRainbow = maxr = maxc = -1;
		
		/* BFS 탐색으로 가장 큰 block 찾기 */

		if (maxBlock == -1) break;

		ans += (maxBlock * maxBlock);

		int visit[MAX][MAX] = { 0 };
		deleteBlock(maxr, maxc, visit, MAP);

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

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (20 + 5)

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

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

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

typedef struct st2
{
	int normal;
	int rainbow;
	int minR;
	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);
}

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

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.minR = 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] == RAINBOW)
			{
				visit[nr][nc] = 1;

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

				if (map[nr][nc] == RAINBOW) blockInfo.rainbow++;

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

		}
	}

	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] == RAINBOW)
			{
				visit[nr][nc] = 1;

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

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

int main()
{
	input();

	int ans = 0;

	while (1)
	{
		int maxBlock, maxRainbow, maxr, maxc;

		maxBlock = maxRainbow = maxr = maxc = -1;
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c] == BLACK || MAP[r][c] == RAINBOW || MAP[r][c] == EMPTY) continue;

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

				if (tmp.normal <= 1) continue;

				/* 크기가 가장 큰 블록의 판단 */
				if ((maxBlock < tmp.normal)
					|| (maxBlock == tmp.normal && maxRainbow < tmp.rainbow)
					|| (maxBlock == tmp.normal && maxRainbow == tmp.rainbow && tmp.minR > maxr)
					|| (maxBlock == tmp.normal && maxRainbow == tmp.rainbow && tmp.minR == maxr && tmp.minC > maxc))
				{
					maxBlock = tmp.normal;
					maxRainbow = tmp.rainbow;
					maxr = tmp.minR;
					maxc = tmp.minC;
				}
			}
		}

		if (maxBlock == -1) break;

		ans += (maxBlock * maxBlock);

		int visit[MAX][MAX] = { 0 };
		deleteBlock(maxr, maxc, visit, MAP);

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

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

	return 0;
}