[G2] 백준 21609번 상어 중학교 C++ 구현, 시뮬레이션, BFS

알고리즘 공부/C++

[G2] 백준 21609번 상어 중학교 C++ 구현, 시뮬레이션, BFS

마달랭 2024. 11. 13. 16:25

리뷰

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

구현 + 구현 + 구현 + 구현 + BFS + ... + 조건 + 조건 + 조건 + 구현 + 구현 + 구현의 지옥 문제

그 많은 변수 중 어느 하나도 잘못된 조건을 가지고 있으면 전혀 다른 답이 출력된다.

문제의 조건도 꽤나 많고 까다로워서 실수하기 좋은 문제 예제만으론 엣지케이스를 잡지 못함

전역 변수

n : 주어지는 맵의 한 변의 길이
m : 맵 상에서 주어지는 일반 블럭의 종류의 개수
ans : 정답을 저장하고 출력하기 위한 변수
lst : 맵 정보를 입력 받고, 시뮬레이션을 진행하기 위한 2차원 정수 배열
v : 매번 오토플레이 시 맵 상에서의 그룹화를 위한 2차원 정수 배열
dx, dy : 4방향 탐색을 위한 방향 배열
Pos : 각 블럭의 위치 좌표를 표시하기 위한 구조체
common : 제거해야 할 일반 블럭의 좌표를 저장할 Pos 타입의 벡터
rainbow : 제거해야 할 무지개 블럭의 좌표를 저장할 Pos 타입의 벡터

함수

1. input

void input()

변수와 맵 정보를 입력 받기 위한 함수

2. bfs

void bfs(int sx, int sy)

너비 우선 탐색을 통해 맵 상의 블럭들을 그룹화 하는 함수

매개변수로 초기 시작 위치의 좌표 sx, sy를 입력 받는다.
Pos타입의 큐 q를 초기화 하고 해당 큐에 초기 좌표를 push 해준다.
현재 그룹의 일반 블럭의 좌표를 저장할 Pos타입의 벡터 common_path를 초기화 하고 초기 좌표를 넣는다.
현재 그룹의 무지개 블럭의 그룹 좌표를 저장할 Pos타입의 벡터 rainbow_path를 초기화 한다.
초기 좌표 위치를 현재 블럭의 번호로 방문 표시 해준다.
정수형 변수 cnt에 그룹 내 블럭의 개수를 저장해 주었다. 초기값을 1로 초기화 해준다.
정수형 변수 rain_cnt에 그룹 내 무지개 블럭의 개수를 저장해 주었다. 초기값은 0
큐가 빌때까지 반복문을 돌리며 4방향으로 탐색을 진행해 준다.
범위 내에 있으면서 이동할 위치의 번호가 0이상이라면 이동을 진행한다.
만약 해당 번호가 내 그룹 번호와 같거나 0이 아니라면 다음 위치를 탐색한다.
만약 이미 내 그룹 번호로 방문처리 되어있는 경우에도 다음 위치를 탐색한다.
위 두 조건에 해당하지 않는다면 다음 블럭을 내 그룹의 번호로 방문처리 해준다.
만약 방문한 위치가 0이라면 rain_cnt를 증가시켜준 뒤 rainbow_path에 좌표를 저장해 준다.
만약 나와 동일한 번호의 블럭이라면 common_path에 좌표를 저장해준다.
cnt를 증가시켜 그룹 내 블럭의 개수를 증가시키고 큐에 해당 위치를 push해준다.
반복문이 종료된 후에는 제거해야할 그룹과 비교하여 교체해야하는지를 판단해 준다.
정수형 변수 csize, rsize에 현재 최적 그룹 common, rainbow의 사이즈를 저장해 준다.
flag를 0으로 초기화 해주고 교체 여부판단을 진행해 준다.
cnt가 csize + rsize보다 크다면 교체를 진행해야 한다, flag를 1로 변경한다.
만약 둘이 동일하다면 다음 조건을 체크 해준다, rain_cnt가 risze가 크다면 flag = 1
동일하다면 다음 조건인 common_path의 첫번째 인자의 x좌표를 비교하고 현재가 더 크다면 flag = 1
동일하다면 다음 조건인 y좌표를 비교하고 현재가 더 크다면 flag = 1
최종적으로 flag가 1일 경우 common, rainbow벡터를 common_path, rainbow_path로 변경해 준다.

3. grav

void grav()

중력을 적용해 줄 함수

n개의 열을 탐색해 주며 중력을 적용하는 시뮬레이션을 실행한다.
정수형 변수 h에 초기 높이인 0으로 초기화 해준다.
시뮬레이션에 사용하기 위한 스택인 정수형 벡터 stack을 초기화 해준다.
h가 n과 동일해 질 때까지 반복문을 수행해 준다.
만약 -1을 만났다면 스택에 쌓인 블럭들을 -1의 위에 스택의 뒤에서부터 쌓아준다.
만약 블럭의 번호가 0이상이라면 스택에 넣어주고 해당 위치를 -2로 변경해 준다.
h를 증가시키며 반복문의 조건에 부합하면 빠져나와준다.
빠져나온 후 스택에 남아있는 블럭이 있을 수 있으므로 맵의 최하단인 n - 1인덱스 부터 블럭을 쌓아준다.

4. spin

void spin()

배열 회전을 진행해줄 함수

5. vprint

void vprint()

그룹화 디버깅을 진행할 함수

6. mprint

void mprint()

현재 맵 정보 디버깅을 진행할 함수

7. autoplay

void autoplay()

오토플레이 시뮬레이션을 진행할 함수

무한 루프를 실행하고 bool형의 변수 flag를 초기값 0인 상태로 초기화 해준다.
memset 메서드를 통해 v배열을 초기화 해주고, common, rainbow벡터도 clear를 진행해 준다.
맵의 위에서부터 탐색을 하며 0이상이면서 방문하지 않은 블럭을 탐색해준다.
조건에 부합하는 블럭을 만났다면 해당 블럭에서 4방향 탐색을 진행한다.
만약 맵의 범위 내이면서 현재 블럭과 번호가 같거나 0이고, 나와 동일한 번호로 방문처리 되어있지 않은 경우 flag를 1로 변경해 주고 현재 블럭의 좌표로부터 bfs를 수행해 준다.
만약 전체 맵을 탐색했으나 flag가 0인 경우 더이상 탐색해도 의미가 없으니 break 처리해 준다.
bfs함수를 통해 구한 rainbow, common벡터에 저장된 좌표를 참조해 준다.
해당 좌표들을 맵 상에서 모두 -2로 변경해 준다.
두 벡터의 size의 합의 제곱만큼의 값을 ans변수에 더해준다.
이후 grav함수 호출 후 spin함수를 호출하고 마지막으로 grav함수를 한번 더 호출해 준다.

문제풀이

input 함수를 통해 값을 입력 받아 변수 및 배열등의 자료 구조를 초기화 해준다.
autoplay 함수를 통해 시뮬레이션을 진행해 주고 ans변수에 정답을 저장해 준다.
ans 변수에 저장된 값을 출력해 준다.

참고 사항

블럭을 참조할때 동일한 번호이거나 0인 인접한 블럭이 1개도 없다면 bfs를 실행할 필요가 없다.
bfs를 돌릴 블럭을 찾을 때 방문 처리가 되지 않은 블럭이 아닌 나와 다른 번호로 방문처리된 블럭도 포함된다.
매 오토 플레이를 진행할 때 사용했던 배열 및 벡터 정보를 초기화 해주어야 한다.
그룹의 기준 블럭은 좌표가 x, y순으로 가장 작은 블럭이며, 제거할 그룹 비교시엔 좌표가 x, y순으로 가장 큰 블럭이다.

정답 코드

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n, m, ans;
int lst[20][20];
int v[20][20];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

struct Pos {
	int x, y;
};

vector<Pos> common;
vector<Pos> rainbow;

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> lst[i][j];
}

void bfs(int sx, int sy) {
	queue<Pos> q;
	vector<Pos> common_path(1, { sx, sy });
	vector<Pos> rainbow_path;
	q.push({ sx, sy });
	v[sx][sy] = lst[sx][sy];
	int cur = lst[sx][sy];
	int cnt = 1;
	int rain_cnt = 0;

	while (!q.empty()) {
		Pos Pos = q.front(); q.pop();
		int cx = Pos.x, cy = Pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			int next = lst[nx][ny];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && next >= 0) {
				if (cur != next && next != 0) continue;
				if (v[nx][ny] == cur) continue;
				v[nx][ny] = cur;
				if (!next) {
					rain_cnt++;
					rainbow_path.push_back({ nx, ny });
				}
				else common_path.push_back({ nx, ny });
				cnt++;
				q.push({ nx, ny });
			}
		}
	}

	int csize = common.size();
	int rsize = rainbow.size();
	int flag = 0;

	if (cnt > csize + rsize) flag = 1;
	else if (cnt == csize + rsize) {
		if (rain_cnt > rsize) flag = 1;
		else if (rain_cnt == rsize) {
			if (common_path[0].x > common[0].x) flag = 1;
			else if (common_path[0].x == common[0].x) {
				if (common_path[0].y > common[0].y) flag = 1;
			}
		}
	}

	if (flag) {
		common = common_path;
		rainbow = rainbow_path;
	}
}

void grav() {
	for (int j = 0; j < n; ++j) {
		int h = 0;
		vector<int> stack;
		while (h < n) {
			if (lst[h][j] == -1 && !stack.empty()) {
				int nh = h;
				while (!stack.empty()) {
					lst[--nh][j] = stack.back();
					stack.pop_back();
				}
			}

			if (lst[h][j] >= 0) {
				stack.push_back(lst[h][j]);
				lst[h][j] = -2;
			}

			h++;
		}

		while (!stack.empty()) {
			lst[--h][j] = stack.back();
			stack.pop_back();
		}
	}
}

void spin() {
	int temp[20][20];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			temp[n - j - 1][i] = lst[i][j];
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			lst[i][j] = temp[i][j];
		}
	}
}

void vprint() {
	cout << "V\n";
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cout << v[i][j] << " ";
		}
		cout << "\n";
	}
}

void mprint() {
	cout << "LST, ans : " << ans << "\n";
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (lst[i][j] >= 0) cout << lst[i][j] << "  ";
			else if (lst[i][j] == -1) cout << lst[i][j] << " ";
			else cout << "   ";
		}
		cout << "\n";
	}
}

void autoplay() {
	while (1) {
		bool flag = 0;
		memset(v, 0, sizeof(v));
		common.clear();
		rainbow.clear();

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (lst[i][j] <= 0 || v[i][j]) continue;
				for (int k = 0; k < 4; ++k) {
					int nx = i + dx[k], ny = j + dy[k];
					if (0 <= nx && nx < n && 0 <= ny && ny < n && (lst[nx][ny] == lst[i][j] || lst[nx][ny] == 0) && v[nx][ny] != lst[i][j]) {
						flag = 1;
						bfs(i, j);
					}
				}
			}
		}
		
		if (!flag) break;

		for (Pos pos : rainbow) lst[pos.x][pos.y] = -2;
		for (Pos pos : common) lst[pos.x][pos.y] = -2;
		ans += pow(rainbow.size() + common.size(), 2);

		//vprint();
		//mprint();
		grav();
		//mprint();
		spin();
		//mprint();
		grav();
		//mprint();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	autoplay();
	cout << ans;
}

728x90

'알고리즘 공부 > C++' 카테고리의 다른 글

[G3] 백준 6087번 레이저 통신 C++ 다익스트라, 플러드 필 (0)	2024.11.15
[P5] 백준 3197번 백조의 호수 C++ 플러드 필, BFS, 유니온 파인드 (0)	2024.11.14
[G5] 백준 21608번 상어 초등학교 C++ 구현 (0)	2024.11.13
[G4] 백준 17144번 미세먼지 안녕! C++ 구현, 시뮬레이션 (1)	2024.11.12
[D4] SWEA [S/W 문제해결 기본] 2일차 - Ladder1 C++ 구현, 시뮬레이션, 브루트포스 알고리즘 (0)	2024.11.11

현재글[G2] 백준 21609번 상어 중학교 C++ 구현, 시뮬레이션, BFS

개인사

개발이 인생인 사람

250x250

백준, boost.asio, 구현, 세그먼트 트리, 시뮬레이션, 다익스트라, 프로그래머스, C++, 브루트포스 알고리즘, 트리, dfs, 파이썬, 완전 탐색, Boost, 백트래킹, 자료 구조, SWEA, 리눅스, BFS, 너비 우선 탐색,

Today :
Yesterday :

개인사