2021.10.07_21609-상어중학교
본문 바로가기
알고리즘 모음집/New 알고리즘

2021.10.07_21609-상어중학교

by KyeongMin 2021. 10. 8.
728x90
반응형

소스코드1

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define SIZE 21
int N, M,answer;
int bnum = 1;
int B[SIZE][SIZE];
int visit[SIZE][SIZE] = { 0, };
int raindow, blockCnt;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
	int y, x, cnt,num,bnum;
};
vector<Data>block;
bool cmp(Data a, Data b) {
	if (a.cnt == b.cnt) {
		if (a.num == b.num) {
			if (a.y == b.y) {
				return a.x > b.x;
			}
			else return a.y > b.y;
		}
		else return a.num > b.num;
	}else return a.cnt > b.cnt;
}
void init();//초기화 및 초기입력
void autoGame();//자동 게임 시작
bool safeZone(int y, int x);
void dfs(int i, int j, int cnt, int num);
void one();//덩어리선택
void two();//제거
//void three();//중력
//void four();//90도 반시계회전

int main(void) {
	int testCase = 1;
	for (int tc = 1; tc <= testCase; tc++) {
		init();
		autoGame();
		printf("%d\n", answer);
	}
	return 0;
}
bool safeZone(int y, int x) {
	return 0 <= y && y < N && 0 <= x && x< N;
}
void dfs(int i, int j, int cnt, int num) {

	for (int dir = 0; dir < 4; dir++) {
		Data n;
		n.y = i + dy[dir]; n.x = j + dx[dir];
		n.cnt = cnt + 1;
		if (safeZone(n.y,n.x)&&visit[n.y][n.x]==0&&(B[n.y][n.x] == -2 || B[n.y][n.x] == num)) {
			if (B[n.y][n.x] ==-2)raindow++;
			blockCnt++;
			visit[n.y][n.x] = bnum;
			dfs(n.y, n.x, n.cnt, num);
		}
	}
}
void one() {
	block.clear();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			memset(visit, 0, sizeof(visit));
			if (B[i][j]!=0&&visit[i][j] == 0 && B[i][j] != -1 && B[i][j] !=-2) {
				raindow = 0; blockCnt = 1;
				bnum++;

				visit[i][j] = bnum;

				dfs(i, j, 1, B[i][j]);
				if (blockCnt == 1) {
					bnum--;
					visit[i][j] = 0;
				}
				if (blockCnt > 1)block.push_back({ i,j,blockCnt,raindow,bnum});
			}
		}
	}
	sort(block.begin(), block.end(), cmp);
}
void two() {
	memset(visit, 0, sizeof(visit));
	bnum = block[0].bnum;
	dfs(block[0].y, block[0].x,1, B[block[0].y][block[0].x]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visit[i][j] == block[0].bnum) {
				B[i][j] =0;
			}
		}
	}
	answer += block[0].cnt*block[0].cnt;
}
void three() {
	for (int j = 0; j < N; j++) {
		deque<int>q;
		for (int i = 0; i < N; i++) {
			if (B[i][j] != 0 && B[i][j] != -1) {
				q.push_back(B[i][j]);
				B[i][j] = 0;
			}
			if (B[i][j] == -1 ) {
				int ci = i;
				while (!q.empty()) {
					B[--ci][j] = q.back(); q.pop_back();
				}
			}
		}
		int i = N - 1;
		while (!q.empty()) {
			B[i--][j] = q.back(); q.pop_back();
		}
	}
}
void four() {
	int C[SIZE][SIZE] = { 0, };
	for (int i = 0; i <N; i++) {
		for (int j = 0; j < N; j++) {
			C[i][j] = B[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			B[i][j] = C[j][N - i-1];
		}
	}
}
void autoGame() {
	while(1) {
		one();
		if (block.size() == 0)break;
		two();
		three();
		four();
		three();
	}
}
void init() {
	N = M = answer = 0;
	bnum = 1;
	memset(B, 0, sizeof(B));
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &B[i][j]);
			if (B[i][j] == 0)B[i][j] = -2;
		}
	}
}

소스코드2

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define SIZE 21
int N, M,answer;
int bnum = 1;
int B[SIZE][SIZE];
int visit[SIZE][SIZE] = { 0, };
int raindow, blockCnt;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
	int y, x, cnt,num,bnum;
};
vector<Data>block;
bool cmp(Data a, Data b) {
	if (a.cnt == b.cnt) {
		if (a.num == b.num) {
			if (a.y == b.y) {
				return a.x > b.x;
			}
			else return a.y > b.y;
		}
		else return a.num > b.num;
	}else return a.cnt > b.cnt;
}

void init();//초기화 및 초기입력
void autoGame();//자동 게임 시작
bool safeZone(int y, int x);
void dfs(int i, int j, int cnt, int num);
void one();//덩어리선택
void two();//제거
void three();//중력
void four();//90도 반시계회전

int main(void) {
	int testCase = 1;
	for (int tc = 1; tc <= testCase; tc++) {
		init();
		autoGame();
		printf("%d\n", answer);
	}
	return 0;
}
bool safeZone(int y, int x) {
	return 0 <= y && y < N && 0 <= x && x< N;
}
void dfs(int i, int j, int cnt, int num) {

	for (int dir = 0; dir < 4; dir++) {
		Data n;
		n.y = i + dy[dir]; n.x = j + dx[dir];
		n.cnt = cnt + 1;
		if (safeZone(n.y,n.x) && visit[n.y][n.x]==0&&(B[n.y][n.x] == -2 || B[n.y][n.x] == num)) {
			
			if (B[n.y][n.x] ==-2)raindow++;
			blockCnt++;
			if (B[n.y][n.x] == -2)visit[n.y][n.x] = -6;
			else visit[n.y][n.x] = bnum;
			dfs(n.y, n.x, n.cnt, num);
		}
	}
}

void one() {
	memset(visit, 0, sizeof(visit));
	block.clear();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (B[i][j]!=0&&visit[i][j] == 0 && B[i][j] != -1 && B[i][j] !=-2) {
				raindow = 0; blockCnt = 1;
				bnum++;

				visit[i][j] = bnum;

				dfs(i, j, 1, B[i][j]);
				if (blockCnt == 1) {
					bnum--;
					visit[i][j] = 0;
				}
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (visit[i][j] == -6)visit[i][j] = 0;
					}
				}
				if (blockCnt > 1)block.push_back({ i,j,blockCnt,raindow,bnum});
			}
		}
	}
	sort(block.begin(), block.end(), cmp);
}
void two() {
	memset(visit, 0, sizeof(visit));
	bnum = block[0].bnum;
	dfs(block[0].y, block[0].x, 1, B[block[0].y][block[0].x]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visit[i][j]!=0) {
				B[i][j] = 0;
			}
		}
	}
	answer += block[0].cnt*block[0].cnt;
}
void three() {
	for (int j = 0; j < N; j++) {
		deque<int>q;
		for (int i = 0; i < N; i++) {
			if (B[i][j] != 0 && B[i][j] != -1) {
				q.push_back(B[i][j]);
				B[i][j] = 0;
			}
			if (B[i][j] == -1 ) {
				int ci = i;
				while (!q.empty()) {
					B[--ci][j] = q.back(); q.pop_back();
				}
			}
		}
		int i = N - 1;
		while (!q.empty()) {
			B[i--][j] = q.back(); q.pop_back();
		}
	}
}
void four() {
	int C[SIZE][SIZE] = { 0, };
	for (int i = 0; i <N; i++) {
		for (int j = 0; j < N; j++) {
			C[i][j] = B[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			B[i][j] = C[j][N - i-1];
		}
	}

}
void autoGame() {
	while(1) {
		one();
		if (block.size() == 0)break;
		two();
		three();
		four();
		three();
	}
}
void init() {
	N = M = answer = 0;
	bnum = 1;
	memset(B, 0, sizeof(B));
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &B[i][j]);
			if (B[i][j] == 0)B[i][j] = -2;
		}
	}
}

설계

실수

  • 실수는 우선 설계할때 무지개 블럭인경우 중복이 가능하게 검사를 하게 해야하는데 그렇게 안함
  • 그리고 그걸 한다고 visit를 그냥 초기화해서 했는데 그렇게 하면 안됨
  • 전체적으로 다행이 블록 내리는것, 블록 반시계로 돌리는것 , 블록 제거하는것은 맞음
  • 문제는 내가 문제를 잘못이해한건지 아니면 문제 번역이 오역인지 유무... 하지만 전자인 경우가 많기때문에 내가 문제를 잘못이해한것으로 생각하고 항상 의심하기

문제 링크

21609-상어중학교

원본

https://github.com/3DPIT/AlgorithmFinal/blob/main/02.algorithmStudy/1007/01.21609-%EC%83%81%EC%96%B4%EC%A4%91%ED%95%99%EA%B5%90/2021.10.07_21609-%EC%83%81%EC%96%B4%EC%A4%91%ED%95%99%EA%B5%90.md#%EC%84%A4%EA%B3%84

 

GitHub - 3DPIT/AlgorithmFinal

Contribute to 3DPIT/AlgorithmFinal development by creating an account on GitHub.

github.com

 

728x90
반응형

'알고리즘 모음집 > New 알고리즘' 카테고리의 다른 글

2021.10.18_12741-두전구  (0) 2021.10.18
2021.10.09_20061-모노미노도미노2  (0) 2021.10.10
2021.10.06_21608-상어초등학교  (0) 2021.10.06
2021.10.05_20058-마법사상어와파이어스톰  (0) 2021.10.06
2021.10.04_20056-마법사상어와파이어볼  (0) 2021.10.05

관련글

댓글

티스토리툴바