민트초코우유

Simulation, BFS

평균 : 180'

---

sol : 187' 38''

• 수행 시간 : 32ms
• 메모리 : 0MB

Learnings

• 비트마스크식 표현 기술
• 정렬 key를 tuple 하나로 압축하는 기술

[Optimized Ver]

[Initial Ver]

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <tuple>
#include <algorithm>

#define MAX_N 51
#define MINT 1
#define CHOCO 10
#define MILK 100

using namespace std;

int n, t;
// 상, 하, 좌, 우
int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
bool visited[MAX_N][MAX_N];
vector<pair<int, int>> orders;

struct Student {
	int power;
	int food;
	bool defend;

	Student() {}
	Student(int _power, int _food, bool _defend) :
		power(_power), food(_food), defend(_defend) { }
};

struct Union {
	int p_r;
	int p_c;
	vector<pair<int, int>> elems;

	Union() {}
	Union(int _p_r, int _p_c) :
		p_r(_p_r), p_c(_p_c) { }
};

Student grid[MAX_N][MAX_N];
vector<Union> unions;

void DebugPower() {
	cout << "DEBUG POWER" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << grid[i][j].power << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void DebugFood() {
	cout << "DEBUG FOOD" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << grid[i][j].food << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void Init() {
	cin >> n >> t;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			char food;
			cin >> food;
			if (food == 'T') grid[i][j] = Student(0, MINT, false);
			else if (food == 'C') grid[i][j] = Student(0, CHOCO, false);
			else if (food == 'M') grid[i][j] = Student(0, MILK, false);
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int _power;
			cin >> _power;
			grid[i][j].power = _power;
		}
	}
}

void Breakfast() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			grid[i][j].power++;
		}
	}
}

///////////////////////////////////////////////////////////////////////////////////////

void InitVisited() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = false;
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

void Undefend() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j].defend) grid[i][j].defend = false;
		}
	}
}

bool NewStronger(Union u, int r, int c) {
	if (grid[u.p_r][u.p_c].power < grid[r][c].power) return true;
	else if (grid[u.p_r][u.p_c].power == grid[r][c].power) {
		if (u.p_r > r) return true;
		else if (u.p_r == r) {
			if (u.p_c > c) return true;
		}
	}

	return false;
}

void GetUnion(int i, int j) {
	queue<pair<int, int>> q;
	q.push({ i, j });
	visited[i][j] = true;
	int curFood = grid[i][j].food;
	Union curUnion = Union(i, j);
	curUnion.elems.push_back({ i, j });

	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (InGrid(ni, nj) && !visited[ni][nj]) {
				if (grid[ni][nj].food == curFood) {
					visited[ni][nj] = true;
					q.push({ ni, nj });
					if (NewStronger(curUnion, ni, nj)) {
						curUnion.p_r = ni, curUnion.p_c = nj;
					}
					curUnion.elems.push_back({ ni, nj });
				}
			}
		}
	}

	unions.push_back(curUnion);

	//cout << "cur union's elem : ";
	//for (int i = 0; i < curUnion.elems.size(); i++) {
	//	if (curUnion.elems[i].first == curUnion.p_r && curUnion.elems[i].second == curUnion.p_c) {
	//		cout << "p";
	//	}
	//	cout << "(" << curUnion.elems[i].first << "," << curUnion.elems[i].second << "), ";
	//}
	//cout << endl;
}

void FormUnions() {
	InitVisited();
	unions.clear();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (visited[i][j]) continue;
			GetUnion(i, j);
		}
	}
}

void Enforce() {
	for (int i = 0; i < unions.size(); i++) {
		for (int e = 0; e < unions[i].elems.size(); e++) {
			// 대표자는 스킵
			if (unions[i].elems[e].first == unions[i].p_r && unions[i].elems[e].second == unions[i].p_c) continue;

			// 나머지는 대표자에게 1씩 넘김
			grid[unions[i].elems[e].first][unions[i].elems[e].second].power--;
			grid[unions[i].p_r][unions[i].p_c].power++;
		}
	}
}

void Lunch() {
	// 1. 그룹 형성
	FormUnions();

	// 2. 대표자에게 신앙심 넘김
	Enforce();
}

///////////////////////////////////////////////////////////////////////////////////////

bool comparator(tuple<int, int, int> a, tuple<int, int, int> b) {
	int p1, r1, c1, p2, r2, c2;
	tie(p1, r1, c1) = a;
	tie(p2, r2, c2) = b;

	if (p1 > p2) return true;
	else if (p1 == p2) {
		if (r1 < r2) return true;
		else if (r1 == r2) {
			if (c1 < c2) return true;
		}
	}

	return false;
}

void GetOrder() {
	vector<Union> group1, group2, group3;
	orders.clear();

	for (int i = 0; i < unions.size(); i++) {
		int curFood = grid[unions[i].p_r][unions[i].p_c].food;
		if (curFood == MINT || curFood == CHOCO || curFood == MILK) group1.push_back(unions[i]);
		else if (curFood == MINT + CHOCO || curFood == MINT + MILK || curFood == CHOCO + MILK) group2.push_back(unions[i]);
		else if (curFood == MINT + CHOCO + MILK) group3.push_back(unions[i]);
	}

	//cout << "before sort group1" << endl;
	//for (int i = 0; i < group1.size(); i++) {
	//	cout << "id " << i << "'s power : " << grid[group1[i].p_r][group1[i].p_c].power << ", (" << group1[i].p_r << "," << group1[i].p_c << "), " << ", food : " << grid[group1[i].p_r][group1[i].p_c].food << endl;
	//}
	//cout << "before sort group2" << endl;
	//for (int i = 0; i < group2.size(); i++) {
	//	cout << "id " << i << "'s power : " << grid[group2[i].p_r][group2[i].p_c].power << ", (" << group2[i].p_r << "," << group2[i].p_c << "), " << ", food : " << grid[group2[i].p_r][group2[i].p_c].food << endl;
	//}
	//cout << "before sort group3" << endl;
	//for (int i = 0; i < group3.size(); i++) {
	//	cout << "id " << i << "'s power : " << grid[group3[i].p_r][group3[i].p_c].power << ", (" << group3[i].p_r << "," << group3[i].p_c << "), " << ", food : " << grid[group3[i].p_r][group3[i].p_c].food << endl;
	//}
	//cout << endl;

	// 그룹 1 세부 정렬
	vector<tuple<int, int, int>> ordered_g1;
	for (int i = 0; i < group1.size(); i++) {
		ordered_g1.push_back(make_tuple(-grid[group1[i].p_r][group1[i].p_c].power, group1[i].p_r, group1[i].p_c));
	}
	sort(ordered_g1.begin(), ordered_g1.end());

	for (int i = 0; i < group1.size();  i++) {
		int r, c;
		tie(ignore, r, c) = ordered_g1[i];
		orders.push_back({ r, c });
	}
	
	// 그룹 2 세부 정렬
	vector<tuple<int, int, int>> ordered_g2;
	for (int i = 0; i < group2.size(); i++) {
		ordered_g2.push_back(make_tuple(-grid[group2[i].p_r][group2[i].p_c].power, group2[i].p_r, group2[i].p_c));
	}
	sort(ordered_g2.begin(), ordered_g2.end());

	for (int i = 0; i < group2.size(); i++) {
		int r, c;
		tie(ignore, r, c) = ordered_g2[i];
		orders.push_back({ r, c });
	}

	// 그룹 3 세부 정렬
	vector<tuple<int, int, int>> ordered_g3;
	for (int i = 0; i < group3.size(); i++) {
		ordered_g3.push_back(make_tuple(-grid[group3[i].p_r][group3[i].p_c].power, group3[i].p_r, group3[i].p_c));
	}
	sort(ordered_g3.begin(), ordered_g3.end());

	for (int i = 0; i < group3.size(); i++) {
		int r, c;
		tie(ignore, r, c) = ordered_g3[i];
		orders.push_back({ r, c });
	}

	//cout << "after sort" << endl;
	//for (int i = 0; i < orders.size(); i++) {
	//	cout << "(" << orders[i].first << "," << orders[i].second << ")" << " -> ";
	//}
	//cout << endl;
}

int MixFood(int a, int b) {
	int mixed = a + b;
	if (mixed / 100 > 1) mixed -= 100;
	if ((mixed / 10) % 10 > 1) mixed -= 10;
	if ((mixed % 10) > 1) mixed -= 1;

	return mixed;
}

void Propagation() {
	for (int i = 0; i < orders.size(); i++) {
		if (grid[orders[i].first][orders[i].second].defend) continue;

		int dir = grid[orders[i].first][orders[i].second].power % 4;
		int desp = grid[orders[i].first][orders[i].second].power - 1;
		grid[orders[i].first][orders[i].second].power = 1;
		int curFood = grid[orders[i].first][orders[i].second].food;
		
		int ci = orders[i].first + ds[dir][0], cj = orders[i].second + ds[dir][1];
		while (InGrid(ci, cj) && desp > 0) {
			// 1. 음식이 완전 같은 경우
			if (grid[ci][cj].food == curFood) {
				ci = ci + ds[dir][0], cj = cj + ds[dir][1];
				continue;
			}

			// 2. 다른 경우
			int targetPower = grid[ci][cj].power;
			grid[ci][cj].defend = true;
			// 2-1. 강한 전파
			if (desp > targetPower) {
				grid[ci][cj].food = curFood;
				desp -= (targetPower + 1);
				grid[ci][cj].power++;
			}
			// 2-2. 약한 전파
			else if (desp <= targetPower) {
				grid[ci][cj].food = MixFood(curFood, grid[ci][cj].food);
				grid[ci][cj].power += desp;
				desp = 0;
			}
		}
	}
}

void Dinner() {
	// 1. 순서 정렬
	GetOrder();

	// 2. 전파
	Propagation();
}

void GetState() {
	int tcm = 0, tc = 0, tm = 0, cm = 0, m = 0, c = 0, t = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int curFood = grid[i][j].food, curPower = grid[i][j].power;
			if (curFood == MINT + CHOCO + MILK) tcm += curPower;
			else if (curFood == MINT + CHOCO) tc += curPower;
			else if (curFood == MINT + MILK) tm += curPower;
			else if (curFood == CHOCO + MILK) cm += curPower;
			else if (curFood == MILK) m += curPower;
			else if (curFood == CHOCO) c += curPower;
			else if (curFood == MINT) t += curPower;
		}
	}

	cout << tcm << " " << tc << " " << tm << " " << cm << " " << m << " " << c << " " << t << '\n';
}

int main() {
	Init();

	for (int day = 1; day <= t; day++) {
		// 0. 방어상태 해제
		Undefend();

		// 1. Breafkast
		Breakfast();

		// 2. Lunch
		Lunch();

		// 3. Dinner
		Dinner();

		GetState();
	}

	return 0;
}