<Baekjoon> #21603 Simulation,Graph,DFS,BFS_상어 중학교 c++

Google 아니고 Joogle·2022년 4월 11일
0

SAMSUNG SW Test

목록 보기
28/39
post-thumbnail

#21609 상어 중학교
배열 회전 참고

💡Solution & Idea

  • 이 문제는 크게 1. 블록을 만드는 부분 2. 중력이 작용하는 부분 3. 격자를 90도 반시계 방향으로 회전하는 부분으로 나눌 수 있다
  • 여러 개의 블록으로 나눌 때 주의해야 할 점은, 무지개 블록은 여러 블록에 포함 될 수 있다는 것이다.
    예를 들어, 다음과 같은 경우에 이 블록은 두 개의 경우로 나눌 수 있다

Initialize & Compare 함수

  • 여러 개의 블록을 관리하기 위해 구조체를 선언
  • 해당 블록 안에 있는 멤버들의 좌표를 저장하는 벡터, 블록의 크기, 무지개 색의 개수, 시작점
struct BLOCK {
	vector<pair<int, int>> v;
	int blockSize;
	int rainbow;
	pair<int, int> start;
};
vector<BLOCK> block;
  • 블록 간 우선 순위를 나타내기 위해 compare 함수 정의
bool compare(const BLOCK& A, const BLOCK& B) {
	if (A.blockSize == B.blockSize)
		if (A.rainbow == B.rainbow)
			if (A.start.first == B.start.first)
				return A.start.second > B.start.second;
			else return A.start.first > B.start.first;
		else return A.rainbow > B.rainbow;
	else return A.blockSize > B.blockSize;
}

1. Make Block

  • 기본적으로 BFS, 너비 우선 탐색을 이용해 하나의 블록을 만드는데, 전체 좌표를 탐색하다가 1~M 사이의 숫자가 나오면 이 지점을 블록의 시작점으로 둔다
  • visited, r_visited 두 개를 두어, 무지개 지점을 방문 했을 때는 r_visited에 방문 표시를 해주고 이번 한 블록을 만들고 나면 다시 초기화 된다 (다른 블록을 만들 때도 다시 방문할 수 있기 때문에)
  • 무지개 지점이 아닌 같은 숫자를 방문 했을 때는 visited에 방문 표시를 해준다
  • 탐색이 끝난 후, 블록의 크기가 2보다 작은 경우 (즉, 1인 경우) block을 비워준다
void makeBlock(int i, int j, int colour) {
	memset(r_visited, false, sizeof(r_visited));

	visited[i][j] = true;
	queue<pair<int, int>> q;
	q.push({ i,j });

	block[blockNum].blockSize++;
	block[blockNum].v.push_back({ i,j });
	block[blockNum].start.first = i;
	block[blockNum].start.second = j;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (map[ny][nx] == BLACK) continue;

			if (map[ny][nx] == RAINBOW && !r_visited[ny][nx]) {
				r_visited[ny][nx] = true;
				block[blockNum].rainbow++;
				block[blockNum].blockSize++;
				block[blockNum].v.push_back({ ny, nx });
				q.push({ ny, nx });
			}

			else if (map[ny][nx] == colour && !visited[ny][nx]) {
				visited[ny][nx] = true;
				block[blockNum].blockSize++;
				block[blockNum].v.push_back({ ny, nx });
				q.push({ ny, nx });

			}
		}
	}

	if (block[blockNum].blockSize ==1) {
		visited[i][j] = false;
		block[blockNum].v.clear();
		block[blockNum].blockSize = 0;
		block[blockNum].rainbow = 0;
		block[blockNum].start.first = 0;
		block[blockNum].start.second = 0;
		return;
	}
	blockNum++;
}

2. Move Down - Gravity

  • N-2번째 행부터 아래로 움직일 수 있는지 탐색해본다
  • 현재 칸이 빈 칸이거나, 검은색 칸이면 움직이지 않는다
  • 아래 칸이 다음 칸이 빈칸이 아닐 때까지 움직여준다
void moveDown() {
	for (int y = N - 2; y >= 0; y--) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == EMPTY || map[y][x]==BLACK) continue;
			int ny = y;
			while (ny<N-1 && map[ny+1][x]==EMPTY)
				ny++;
			if (ny != y) {
				map[ny][x] = map[y][x];
				map[y][x] = EMPTY;
			}
		}
	}
}

3. Rotate

  • 격자를 회전하는 부분은 이제 그냥 암기
  • 반시계 방향 90도 회전
void rotate() {
	int tmp[MAX][MAX];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tmp[i][j] = map[i][j];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = tmp[j][N - 1 - i];
}
  • 시계 방향 90도 회전
void rotate() {
	int tmp[MAX][MAX];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tmp[i][j] = map[i][j];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = tmp[N-i-j][i];
}

Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>

const int MAX = 21;
const int EMPTY = -2;
const int BLACK = -1;
const int RAINBOW = 0;

const int dy[] = { 1,-1,0,0 };
const int dx[] = { 0,0,1,-1 };

using namespace std;

struct BLOCK {
	vector<pair<int, int>> v;
	int blockSize;
	int rainbow;
	pair<int, int> start;
};
vector<BLOCK> block;
int ret = 0;
int N, M, blockNum=0;

vector<vector<int>> map;
bool visited[MAX][MAX], r_visited[MAX][MAX];

bool compare(const BLOCK& A, const BLOCK& B) {
	if (A.blockSize == B.blockSize)
		if (A.rainbow == B.rainbow)
			if (A.start.first == B.start.first)
				return A.start.second > B.start.second;
			else return A.start.first > B.start.first;
		else return A.rainbow > B.rainbow;
	else return A.blockSize > B.blockSize;
}
void input() {
	cin >> N >> M;
	map = vector<vector<int>>(N, vector<int>(N));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	block = vector<BLOCK>(MAX * MAX / 2);
}
void init() {
	memset(visited, 0, sizeof(visited));

	for (int i = 0; i < blockNum; i++) {
		block[i].v.clear();
		block[i].blockSize = 0;
		block[i].rainbow = 0;
		block[i].start.first = 0;
		block[i].start.second = 0;
	}

	blockNum = 0;
}

void makeBlock(int i, int j, int colour) {
	memset(r_visited, false, sizeof(r_visited));

	visited[i][j] = true;
	queue<pair<int, int>> q;
	q.push({ i,j });

	block[blockNum].blockSize++;
	block[blockNum].v.push_back({ i,j });
	block[blockNum].start.first = i;
	block[blockNum].start.second = j;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (map[ny][nx] == BLACK) continue;

			if (map[ny][nx] == RAINBOW && !r_visited[ny][nx]) {
				r_visited[ny][nx] = true;
				block[blockNum].rainbow++;
				block[blockNum].blockSize++;
				block[blockNum].v.push_back({ ny, nx });
				q.push({ ny, nx });
			}

			else if (map[ny][nx] == colour && !visited[ny][nx]) {
				visited[ny][nx] = true;
				block[blockNum].blockSize++;
				block[blockNum].v.push_back({ ny, nx });
				q.push({ ny, nx });

			}
		}
	}

	if (block[blockNum].blockSize ==1) {
		visited[i][j] = false;
		block[blockNum].v.clear();
		block[blockNum].blockSize = 0;
		block[blockNum].rainbow = 0;
		block[blockNum].start.first = 0;
		block[blockNum].start.second = 0;
		return;
	}
	blockNum++;
}

void rotate() {
	int tmp[MAX][MAX];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tmp[i][j] = map[i][j];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = tmp[j][N - 1 - i];
}

void moveDown() {
	for (int y = N - 2; y >= 0; y--) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == EMPTY || map[y][x]==BLACK) continue;
			int ny = y;
			while (ny<N-1 && map[ny+1][x]==EMPTY)
				ny++;
			if (ny != y) {
				map[ny][x] = map[y][x];
				map[y][x] = EMPTY;
			}
		}
	}
}
void getScore() {
	ret += (block[0].blockSize * block[0].blockSize);
	for (int i = 0; i < block[0].v.size(); i++) {
		int y = block[0].v[i].first;
		int x = block[0].v[i].second;
		map[y][x] = EMPTY;
	}
}
void solution() {
	while (true) {

		init();

		for (int i = 0; i< N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] >= 1 && map[i][j] <= M && !visited[i][j]) 
					makeBlock(i, j, map[i][j]);
			}
		}

		if (blockNum == 0) break;
		sort(block.begin(),block.end(), compare);
		getScore();
		moveDown();
		rotate();

		moveDown();
	}
}

int main() {
	input();
	solution();
	cout << ret << endl;
	return 0;
}

profile
Backend 개발자 지망생

0개의 댓글