< 백준 BaekJoon : 20058번 마법사 상어와 파이어스톰 > C++

<< 문제 >>

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

20058번: 마법사 상어와 파이어스톰

 

 

문제가 좀 말을 이상하게 하는데, 그냥 문제에 적힌 순서 그대로 진행하시면 됩니다. 

 

1. 90도를 기준으로 Rotate 해주기

    - 방법에 따라 다르지만, L의 크기를 기준으로 임시 Table을 만들어서 교체용 Table을 계산하고 계산이 끝나면 진짜 Table에 교체해준다. 

 

2. 얼음을 검사해주는데, 검사하면서 주변에 얼음이 부족하다고 바로 1을 빼버리면, 추후 계산에서 현재 Turn에 1이어야 할 블록이 앞선 계산으로 0이 되어 추가적인 차감이 발생할 수 있다. 

따라서, 빼야할 좌표들을 담아두고, 턴이 끝날때 한번에 빼주는 것이 좋다. 

 

3. 얼음의 총합 계산한다.

 

4. DFS로 얼음 뭉떵이를 계산해준다. 

 

끝

 

<< 코드 >>  

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int n, q;
int TableSize;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

void DivideAndRotate(int& _y, int& _x, int& size, vector<vector<int>>& Table) {
	vector<vector<int>> TempTable(size, vector<int>(size));

	for (int y = 0; y < size; y++) {
		for (int x = 0; x < size; x++) {
			TempTable[x][size - 1 - y] = Table[_y + y][_x + x];
		}
	}

	for (int y = 0; y < size; y++) {
		for (int x = 0; x < size; x++) {
			Table[_y + y][_x + x] = TempTable[y][x];
		}
	}

}

void Rotate(int& l, vector<vector<int>>& Table) {
	int size = pow(2, l);
	//cout << endl << size << endl;

	for (int y = 0; y < TableSize; y += size) {
		for (int x = 0; x < TableSize; x += size) {
			DivideAndRotate(y, x, size, Table);
		}
	}
}


void IceCheck(vector<vector<int>>& Table) {
	queue<pair<int,int>> q;
	for (int y = 0; y < TableSize; y++) {
		for (int x = 0; x < TableSize; x++) {
			// Ice Count
			int count = 0;
			// -1,0 / 0,-1 / 0,1 / 1,0
			if (x - 1 >= 0 && Table[y][x - 1] > 0) {
				count++;
			}
			if (y - 1 >= 0 && Table[y - 1][x] > 0) {
				count++;
			}
			if (x + 1 < TableSize && Table[y][x + 1] > 0) {
				count++;
			}
			if (y + 1 < TableSize && Table[y + 1][x] > 0) {
				count++;
			}

			// 인접에 3개 미만이고, 0이 아닐 때 
			// 지금 빼면 나중에 계산에 영향을 줄 수 있으니 이번 턴에 빼질 값들을 다 모아두고 한번에 빼줌
			if (count < 3 && Table[y][x] > 0) {
				q.push(make_pair(y, x));
			}
		}
	}

	// 빼주어야 하는 좌표, 빼기
	while (!q.empty()) {
		pair<int, int> p = q.front();
		Table[p.first][p.second] -= 1;
		q.pop();
	}
}

int SumIce(vector<vector<int>>& Table) {
	int sum = 0;

	for (auto& y : Table) {
		for (auto& x : y) {
			sum += x;
		}
	}

	return sum;
}


int dfs(int y, int x, vector<vector<bool>>& Visit, vector<vector<int>>& Table) {
	Visit[y][x] = true;
	int ret = 1;
	for (int i = 0; i < 4; i++) {
		int newX = x + dx[i];
		int newY = y + dy[i];

		if (newX < 0 || newX >= TableSize || newY < 0 || newY >= TableSize) continue;
		if (Visit[newY][newX] || Table[newY][newX] == 0) continue;
		ret += dfs(newY, newX, Visit, Table);
	}
	return ret;
}

int main() {
	
	cin >> n >> q;
	TableSize = pow(2, n);

	vector<vector<int>> Table(TableSize,vector<int>(TableSize));

	for (int i = 0; i < TableSize; i++) {
		for (int j = 0; j < TableSize; j++) {
			cin >> Table[i][j];
		}
	}

	for (int i = 0; i < q; i++) {
		int l;
		cin >> l;
		Rotate(l, Table);
		IceCheck(Table);
	}

	// 얼음 총합
	int sum = SumIce(Table);
	
	// MaxIce 뭉텅이
	vector<vector<bool>> VisitTable(TableSize, vector<bool>(TableSize, false));
	int MaxIce = 0;
	for (int y = 0; y < TableSize; y++) {
		for (int x = 0; x < TableSize; x++) {
			if (Table[y][x] > 0 && !VisitTable[y][x]) {
				MaxIce = max(MaxIce, dfs(y, x, VisitTable, Table));
			}
				
		}
	}

	//  result
	cout << sum << '\n' << MaxIce;

}

 

 

<< GitHub >> 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Gold/20058.%E2%80%85%EB%A7%88%EB%B2%95%EC%82%AC%E2%80%85%EC%83%81%EC%96%B4%EC%99%80%E2%80%85%ED%8C%8C%EC%9D%B4%EC%96%B4%EC%8A%A4%ED%86%B0

StudyAlgorithm_Part2/백준/Gold/20058. 마법사 상어와 파이어스톰 at main · J2on/StudyAlgorithm_Part2