[백준 21609] 상어 중학교

++22.11.04 다시 풀어보았다. 

엣지 케이스들이 많았던 문제... 

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

 

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
int N, M;
int A[20 + 2][20 + 2];

struct _st
{
	int x, y;
};
std::queue<_st> Q;
std::vector<_st> V;
int visited[20 + 2][20 + 2];

std::vector<_st> T;
std::vector<_st> RB;


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
}

int BFS(int x, int y, int color)
{
	int dir_x[4] = { 0, 0 ,1 , -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q = {};
	T.clear();

	Q.push({ x, y });
	T.push_back({ x, y });	// 기준좌표 (x, y)에서 만들어진 블록그룹 좌표 정보 저장
    						// 가장 큰 블록그룹 V 갱신할 때 쓸것임
	visited[x][y] = 1; 
	int cnt_rb = 0;
	

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny]) continue;
			if (A[nx][ny] == -1) continue;	// 검은색 블록은 포함되면 안됨 
			if (A[nx][ny] == -2) continue;	// 삭제된 블록은 포함되면 안됨 
			if (A[nx][ny] > 0 && A[nx][ny] != color) continue;
			if (A[nx][ny] == 0) {
				cnt_rb++;
				RB.push_back({ nx, ny });
			}
			Q.push({ nx, ny });
			visited[nx][ny] = 1;	
			T.push_back({ nx, ny });	
		}
	}
	return cnt_rb;
}


void undo_rainbow()	// 무지개 블록은 여러 번 방문할 수 있다... 
{
	for (_st v : RB) {
		visited[v.x][v.y] = 0;
	}
	RB.clear();
}


bool find_group()	// 가장 큰 블록 그룹을 찾는다.
{
	int max_size = -1;
	int max_rb_cnt = -1;
	int max_row = -1;
	int max_col = -1;
	V.clear();
	memset(visited, 0, sizeof(visited));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {	// (i, j) : 기준블록
			if (visited[i][j]) continue;
			if (A[i][j] == -2) continue;	// 삭제된 블록
			if (A[i][j] == -1) continue;
			if (A[i][j] == 0) continue;		// 블록 그룹의 기준 블록은 무지개 블록이 아님
			int rb = BFS(i, j, A[i][j]);	// 무지개 블록 수 리턴
			undo_rainbow();
			int tmp_size = T.size();

			if (tmp_size < 2) continue;		// 그룹에 속한 블럭의 개수는 2보다 크거나 같아야 한다 
			if ((max_size < tmp_size) ||
				(max_size == tmp_size && max_rb_cnt < rb) ||
				(max_size == tmp_size && max_rb_cnt == rb && max_row < i) ||
				(max_size == tmp_size && max_rb_cnt == rb && max_row == i && max_col < j)) {
				V.clear();
				V = T;
				max_size = tmp_size;
				max_rb_cnt = rb;
				max_row = i;
				max_col = j;
			}
		}
	}
	if (V.empty()) return false;
	return true;
}


int del_group()
{
	for (_st v : V) {
		A[v.x][v.y] = -2;
	}
	return V.size();
}



void gravity()
{
	std::queue<std::pair<_st, int>> G;

	// 열마다 돌면서 끌어내려 준다. 
	for (int j = 0; j < N; j++) {
		G = {};
		for (int i = N - 1; i >= 0; i--) {
			if (A[i][j] == -2) continue;
			G.push({ { i, j }, A[i][j] });
			A[i][j] = -2;
		}
		int row = N - 1;
		while (!G.empty()) {
			int x = G.front().first.x;
			int y = G.front().first.y;
			int color = G.front().second;
			G.pop();
			if (color == -1) {
				A[x][y] = color;
				row = x - 1;
				continue;
			}
			A[row][j] = color;
			row--;
		}
	}
}


void rotate_CCW90()
{
	int tmp[20 + 2][20 + 2] = { 0, };
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			tmp[i][j] = A[j][N - 1 - i];
		}
	}
	memcpy(A, tmp, sizeof(A));
}


int auto_play()
{
	int score = 0;
	while (1) {
		if (!find_group()) return score;
		int B = del_group();
		score += (B * B);
		gravity();
		rotate_CCW90();
		gravity();
	}
}



int main()
{
	input();
	int ans = auto_play();
	printf("%d\n", ans);
	return 0;
}

참고로 위에 코드는 4ms 이다. 

0ms 나오는 코드는 중력 작용 할 때, 루프 다 돌리고 채워넣는 것이 아니라 검은색 블록을 만났을 때 마다 그 전까지 칸 채워넣어주면서 진행했다. 

해당 부분의 함수는 아래와 같다. 

void gravity()
{
	std::queue<int> G;

	// 열마다 돌면서 끌어내려 준다. 
	for (int j = 0; j < N; j++) {
		G = {};
		int row = N - 1;
		for (int i = N - 1; i >= 0; i--) {
			if (A[i][j] == -1) {
				while (!G.empty()) {	// 일단 큐 돌만큼 돌고 
					A[row][j] = G.front();
					G.pop();
					row--;
				}
				row = i - 1;	// row를 -1인 칸보다 한 칸 위로 갱신
			}
			if (A[i][j] != -2 && A[i][j] != -1) {
				G.push(A[i][j]);
				A[i][j] = -2;
			}
		}
		while (!G.empty()) {
			A[row][j] = G.front();
			G.pop();
			row--;
		}
	}
}

근데 루프 다 돌고 나와서 조건문으로 검은색 블록일때랑 아닐때 나눠서 채워주는 것이 논리적으로 따라가기 더 쉬운 것 같아서 해당 코드 먼저 올려놓았다. 

 

그리고 엣지 케이스를 또 생각 못하고 틀렸는데 ... "무지개 블록을 중복 방문할 수 있다"는 점이다. 

해당 조건 처리를 안해주면 아마 들어가자마자 틀릴 것.... 

나는 이것을 그나마 쉽게 처리하려고 벡터에 무지개 블록 좌표 다 담아주고 루프 한번 돌리면서 0으로 바꿔주도록 했다. 

---

++22.11.10 복습인데 백준에서 풀기 싫을 때 

 

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

코드트리

#include <cstdio>
#include <cstring>
#include <queue>
int N, M;	// 격자크기 20 N // 폭탄 종류 M
int board[20 + 2][20 + 2];
int rot[20 + 2][20 + 2];
int dest[20 + 2][20 + 2];
int total;

struct _st
{
	int x, y;
};
std::vector<_st> T;	// 임시저장용
std::vector<_st> V;

std::queue<_st> Q;
int visited[20 + 2][20 + 2];


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
}


int BFS(int x, int y, int color)
{
	// init
	T.clear();
	Q = {};

	// dir
	int dir_x[4] = { 0, 0 ,1 , -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ x, y });
	visited[x][y] = 1;
	T.push_back({ x, y });
	int red = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == -2) continue;	// 이미 없어진 폭탄
			if (board[nx][ny] == -1) continue; // 돌
			if (board[nx][ny] != 0 && board[nx][ny] != color) continue;	// 빨간색 아니고 색깔 다름
			if (board[nx][ny] == 0) {	// 빨간색
				Q.push({ nx, ny });
				visited[nx][ny] = 1;
				T.push_back({ nx, ny });
				red++;
				continue;
			}
			if (board[nx][ny] == color) {	// 같은 색
				Q.push({ nx, ny });
				visited[nx][ny] = 1;
				T.push_back({ nx, ny });
				continue;
			}
		}
	}
	return red;
}


void undo_red()
{
	for (_st v : T) {
		if (board[v.x][v.y] == 0) visited[v.x][v.y] = 0;
	}
}



bool Flood_Fill()
{
	memset(visited, 0, sizeof(visited));
	V.clear();

	int max_size = V.size();
	int min_red = 0x7fffffff;
	int max_row = 0;
	int min_col = 0x7fffffff;

	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == -1 || board[i][j] == 0 || board[i][j] == -2) continue;
			if (visited[i][j]) continue;

			int cnt = BFS(i, j, board[i][j]);
			undo_red();
			int size = T.size();
			if (size < 2) continue;
			if ((max_size < size) ||
				(max_size == size && min_red > cnt) ||
				(max_size == size && min_red == cnt && max_row < i) ||
				(max_size == size && min_red == cnt && max_row == i && min_col > j)) {
				max_size = size;
				min_red = cnt;
				max_row = i;
				min_col = j;
				V.clear();
				V = T;	// 컨테이너 바꿈
			}
		}
	}

	// 선택된 폭탄 묶음 제거
	int score = V.size();
	if (score == 0) return false;

	for (_st v : V) {
		board[v.x][v.y] = -2;
	}
	total += (score * score);
	return true;
}


void gravity()
{
	// init
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			rot[i][j] = -2;
		}
	}

	std::queue<int> G;

	for (int j = 0; j < N; j++) {
		G = {};
		int row = N - 1;
		for (int i = N - 1; i >= 0; i--) {
			if (board[i][j] == -1) {
				while (!G.empty()) {
					rot[row][j] = G.front();
					G.pop();
					row--;
				}
				rot[i][j] = -1;
				row = i - 1;	// 돌은 중력의 영항을 받지 않음
			}
			else if (board[i][j] != -2) G.push(board[i][j]);
		}
		while (!G.empty()) {
			rot[row][j] = G.front();
			G.pop();
			row--;
		}
	}
	memcpy(board, rot, sizeof(rot));
}

void rotate_ccw90()
{
	memset(dest, 0, sizeof(dest));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dest[i][j] = board[j][N - 1 - i];
		}
	}

	memcpy(board, dest, sizeof(dest));
}


void simulation()
{
	while (1) {
		if (!Flood_Fill()) return;
		gravity();
		rotate_ccw90();
		gravity();
	}
}


int main()
{
	input();
	simulation();
	printf("%d\n", total);
	return 0;
}

같은문제 설명만 달라져도 초면인 것 같은 매직..... 

---

사실 이전에 풀 때도 만만치 않게 틀림 ㅋ

ㅋㅋ.... 디버깅 실패의 흔적

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
int N, M;	// 격자 크기, 색상 개수
int board[20 + 2][20 + 2];	// -1검은블록  0무지개블록 1~M색상블록  -2삭제된블록 
int gx, gy;			// 삭제할 그룹 시작
int grp_sz, grp_rb;	//	삭제할 그룹 사이즈, 무지개 블록수
int sz, nm, rb;		// 탐색할 그룹 사이즈, 무지개 블록수

struct _st	// 큐용 
{	
	int x, y;
	int type;
};

int visited[20 + 2][20 + 2];
int delv[20 + 2][20 + 2];

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
}

void BFS(int x, int y)
{
	// 초기화
	sz = 0, nm = 1, rb = 0;

	// 초기상태
	std::queue<_st> Q;
	Q.push({ x, y, board[x][y] });
	visited[x][y] = 1;
	int Type = board[x][y];

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;	// 영역 밖이라면 스루
			if (visited[nx][ny]) continue;								// 방문했다면 스루
			if (board[nx][ny] == -1 || board[nx][ny] == -2) continue;	// 검은 블록이거나 삭제된 블록 스루
			if (board[nx][ny] == 0) {	// 무지개색 블록이라면 
				rb++;
				Q.push({ nx, ny, board[nx][ny] });
				visited[nx][ny] = 1;
				continue;
			}
			if (board[nx][ny] == Type) {
				nm++;
				Q.push({ nx, ny, board[nx][ny] });
				visited[nx][ny] = 1;
				continue;
			}
		}
	}
	sz = nm + rb;
}


void init_rb()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 0) visited[i][j] = 0;
		}
	}
}


void get_group()
{
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	gx = gy = 0;
	grp_sz = grp_rb = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == -2 || board[i][j] == -1 || board[i][j] == 0) continue;	// 삭제되었거나 검정색이거나 무지개색이면 스루 
			if (visited[i][j]) continue;
			BFS(i, j);		// 일반 블록에서만 탐색함 
			init_rb();
			if (sz < 2) continue;		// 그룹에 속한 블록의 개수는 2보다 크거나 같아야 한다... 나도 같은 실수 했음.... 킁.. 
										// 만약에 여기서 안걸리면 grp_sz가 갱신되지 않음 .. 즉 그룹이 안만들어졌다는 것이다. 
			if ((grp_sz < sz) ||
				(grp_sz == sz && grp_rb < rb) ||
				(grp_sz == sz && grp_rb == rb && gx < i) ||
				(grp_sz == sz && grp_rb == rb && gx == i && gy < j)) {
				grp_sz = sz;
				grp_rb = rb;
				gx = i;
				gy = j;
			}
		}
	}
	//printf("[g]%d %d %d %d\n", gx, gy, grp_sz, grp_rb);
}



int del_group()
{
	// 초기화
	std::fill(&delv[0][0], &delv[0][0] + sizeof(delv) / sizeof(int), 0);

	// 초기상태
	std::queue<_st> Q;
	Q.push({ gx, gy, board[gx][gy] });
	delv[gx][gy] = 1;
	int Type = board[gx][gy];
	board[gx][gy] = -2;
	int del = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;	// 영역 밖이라면 스루
			if (delv[nx][ny]) continue;									// 방문했다면 스루
			if (board[nx][ny] == -1 || board[nx][ny] == -2) continue;	// 검은 블록이거나 삭제된 블록 스루
			if (board[nx][ny] == 0) {	// 무지개색 블록이라면 
				board[nx][ny] = -2;
				Q.push({ nx, ny, board[nx][ny] });
				delv[nx][ny] = 1;
				del++;
				continue;
			}
			if (board[nx][ny] == Type) {
				board[nx][ny] = -2;
				Q.push({ nx, ny, board[nx][ny] });
				delv[nx][ny] = 1;
				del++;
				continue;
			}
		}
	}
	return del;
}


void gravity()
{
	std::queue<_st> Q;
	for (int j = 0; j < N; j++) {
		Q = {};
		for (int i = N - 1; i >= 0; i--) {
			if (board[i][j] == -2) continue;
			Q.push({ i, j, board[i][j] });
			board[i][j] = -2;
		}
		int row = N - 1;
		while (!Q.empty()) {
			_st data = Q.front();
			Q.pop();

			if (data.type == -1) {
				board[data.x][j] = -1;
				row = data.x - 1;
				continue;
			}
			board[row][j] = data.type;
			row--;
		}
	}
}


void rotate_CCW()
{
	int tmp_board[20 + 2][20 + 2];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			tmp_board[i][j] = board[j][N - i - 1];
		}
	}
	std::fill(&board[0][0], &board[0][0] + sizeof(board) / sizeof(int), 0);
	memcpy(board, tmp_board, sizeof(tmp_board));
}




int simul()
{
	int total = 0;
	while (1) {
		get_group();
		if (grp_sz == 0) return total;	// 그룹이 만들어지지 않았다면 루프를 종료한다. 
		int B = del_group();
		total += (B * B);
		gravity();
		rotate_CCW();
		gravity();
	}
}


int main()
{
	input();
	int score = simul();
	printf("%d\n", score);
	return 0;
}

뚜드려 맞다보면 늘겠zi.... 

혹시 상어중학교 72%에서 틀리고 내 블로그에 찾아왔다면 그룹을 만드는 함수를 마치고 그룹이 생겼는지 생기지 않았는지를 확인했는지 살펴보자...