(c++)백준 21609번: 상어 중학교

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

21609번: 상어 중학교

[풀이]

구현한 것(함수)

1. 블록그룹 정보 저장 함수(bfs)-> vector에 저장하여 sort 활용하여 가장 큰 그룹 찾기

2. 가장 큰 블록 삭제하는 함수(bfs)

3. 블록들을 밑으로 내리는 함수

4. 시계 반대 방향으로 90도 돌리는 함수(바깥 -> 안 순서로 돌리기)

 

#include <iostream>
#include <algorithm>//sort
#include <cstring>//memset
#include <vector>
#include <cmath>//pow
#include <queue>
using namespace std;

struct Pos {
	int x, y;
};

struct Group {
	int x, y;//기준블록 좌표
	int s;//그룹 크기
	int rainbow;//무지개 블록 수
};

bool sortGroup(const Group &A, const Group &B) {
	//크기가 같으면
	if (A.s == B.s) {
		//무지개 블록 수가 같으면
		if (A.rainbow == B.rainbow) {
			//기준 블록 행 같으면
			if (A.x == B.x) {
				//기준 블록 열이 가장 큰 것
				return A.y > B.y;
			}
			else {
				return A.x > B.x;
			}
		}
		else {
			return A.rainbow > B.rainbow;
		}
	}
	return A.s > B.s;
	
}

int N, M;
bool visited[20][20] = {false,};
bool rvisited[20][20] = { false, };
int Map[20][20];
int Score = 0;
vector<Group>group;
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

//각 그룹의 크기, 무지개 블록 수 구하기
void getInfo(int startx, int starty) {
	queue<Pos>q;
	visited[startx][starty] = true;
	q.push({ startx,starty });
	int color = Map[startx][starty];
	int groupSize = 1;
	int rainbowCnt = 0;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<0 || nx>=N || ny<0 || ny>=N)
				continue;
			//다음 블록이 무지개블록이면
			if (Map[nx][ny] == 0 && rvisited[nx][ny] == false) {
				rvisited[nx][ny] = true;
				rainbowCnt++;
				groupSize++;
				q.push({ nx,ny });
			}
			//다음 블록이 같은 블록이면
			else if (color == Map[nx][ny] && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				groupSize++;
				q.push({ nx,ny });
			}
		}
	}
	if(groupSize >= 2)
		group.push_back({ startx,starty,groupSize,rainbowCnt });
}

//블록 제거
void EraseBlock(int startx, int starty) {
	queue<Pos>q;
	q.push({ startx,starty });
	int color = Map[startx][starty];
	Map[startx][starty] = -2;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<0 || nx>=N || ny<0 || ny>=N)
				continue;
			//다음 블록이 무지개블록이거나 같은 블록이면
			if (Map[nx][ny] == 0 || Map[nx][ny] == color) {
				Map[nx][ny] = -2;
				q.push({ nx,ny });
			}
		}
	}
}

//중력 작용
void Gravity() {
	for (int i = N - 2; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			//검은 블록이거나 없으면
			if (Map[i][j] == -1 || Map[i][j] == -2)
				continue;
			int x = i + 1;
			//다른 블록 있을 때까지
			while (Map[x][j] == -2 && x < N) {
				x++;
			}
			//다른 블록이 있거나 범위 밖
			x--;
			if (Map[x][j] == -2) {
				Map[x][j] = Map[i][j];
				Map[i][j] = -2;
			}
		}
	}
}

void Rolling() {
	vector<int>tmp;
	int start = 0;
	int dest = N;
	while (start<N/2) {
		//위 블록 저장
		for (int i = start; i < dest ; i++) {
			tmp.push_back(Map[start][i]);
		}
		//오->위
		for (int i = start; i < dest ; i++) {
			Map[start][i] = Map[i][dest - 1];
		}
		//아래->오
		for (int i = dest - 1; i >= start; i--) {
			Map[dest - 1 - i+start][dest - 1] = Map[dest - 1][i];
		}
		//왼->아래
		for (int i = dest - 1; i >= start; i--) {
			Map[dest - 1][i] = Map[i][start];
		}
		//위->왼
		int d = 0;
		for (int i = dest - 1; i >= start; i--) {
			Map[i][start] = tmp[d++];
		}
		start++;
		dest--;
		tmp.clear();
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
		}
	}
	while (1) {
		//블록 그룹 존재하는지도 확인
		//크기 가장 큰 블록 찾기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				memset(rvisited, false, sizeof(rvisited));
				if (Map[i][j] > 0 && visited[i][j]==false) {
					getInfo(i, j);
				}
			}
		}
		/*
		cout << "초기" << '\n' << '\n';
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << Map[i][j] << ' ';
			}
			cout << '\n';
		}cout << '\n';
		*/
		//그룹 없으면 끝
		if (group.size()==0)
			break;

		//크기 가장 큰 그룹이 앞에 오도록 정렬
		sort(group.begin(), group.end(), sortGroup);

		//가장 큰 그룹 블록 삭제, 점수 획득
		EraseBlock(group[0].x, group[0].y);
		//cout << group[0].s << '\n';
		Score += pow(group[0].s, 2);
		//cout << "score : " << Score << '\n' << '\n';
		/*
		cout << "제거" << '\n' << '\n';
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << Map[i][j] << ' ';
			}
			cout << '\n';
		}cout << '\n';
		*/
		//중력
		Gravity();
		/*
		cout << "중력" << '\n' << '\n';
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << Map[i][j] << ' ';
			}
			cout << '\n';
		}cout << '\n';
		*/
		//90도 반시계 방향 회전
		Rolling();
		/*
		cout << "회전" << '\n' << '\n';
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << Map[i][j] << ' ';
			}
			cout << '\n';
		}cout << '\n';
		*/
		//중력
		Gravity();
		/*
		cout << "중력2" << '\n' << '\n';
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << Map[i][j] << ' ';
			}
			cout << '\n';
		}cout << '\n';
		*/
		memset(visited, false, sizeof(visited));
		group.clear();
	}
	cout << Score<< '\n';
	return 0;
}