미생물연구

Simulation, BFS

평균 : 180'

---

sol : 187' 24''

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

Learnings

• 상태 관리를 좀 더 명확하게 하자. 로직은 전부 맞게 짰는데, 상태 관리를 동기화해서 업데이트 해주지 않은 실수로 디버깅에 1시간 넘게 잡아먹혔다.
• 즉, 상태 관리 요소가 많아질수록 실수가 발생할 확률이 매우 높아진다.
• 이번 문제에서도 area를 굳이 관리할 필요가 없었다. grid로 바로 해결 가능.
• 인접칸 점수 합산 로직에서도 adg[q][q]로 관리해서 둘이 인접한 관계만 놓고 계산했으면 훨씬 쉬웠음.

adj[a][b] = true;
adj[b][a] = true;

for (int a = 1; a <= q; a++) {
	for (int b = a + 1; b <= q; b++) {
    	if (adj[a][b]) score += viruses[a].size * viruses[b].size;
    }
}

Initial Code

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

using namespace std;

#define MAX_N 20
#define EMPTY 0

int n, q;
// 상, 하, 좌, 우
const int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

//  r: 1 ~ n, c: 1 ~ n
int grid[MAX_N][MAX_N];
int tempGrid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
vector<bool> onGrid;

struct Virus {
	int size;
	vector<pair<int, int>> area;

	Virus() {};
};

vector<Virus> viruses;

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

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

	viruses.resize(q + 1);
	for (int v = 1; v <= q; v++) {
		// 좌측 하단, 우측 상단
		int i1, j1, i2, j2;
		cin >> i1 >> j1 >> i2 >> j2;
		for (int i = i1 + 1; i <= i2; i++) {
			for (int j = j1 + 1; j <= j2; j++) {
				viruses[v].area.push_back({ i, j });
			}
		}
		viruses[v].size = (i2 - i1) * (j2 - j1);
	}

	onGrid.resize(q + 1, false);
}

void InitV() {
	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 GetArea(int i, int j, int id) {
	queue<pair<int, int>> q;

	q.push({ i, j });
	visited[i][j] = true;

	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] && grid[ni][nj] == id) {
				q.push({ ni, nj });
				visited[ni][nj] = true;
			}
		}
	}
}

void Delete(int del_id) {
	for (int da = 0; da < viruses[del_id].area.size(); da++) {
		int ci, cj;
		tie(ci, cj) = viruses[del_id].area[da];
		if (grid[n + 1 - cj][ci] == del_id) grid[n + 1 - cj][ci] = EMPTY;
	}

	onGrid[del_id] = false;
}

void CheckDividen() {
	InitV();
	vector<bool> checked;
	checked.resize(q + 1, false);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] == EMPTY || visited[i][j]) continue;

			// 다른 곳에서 또 발견된다는 건 나눠졌다는 뜻
			if (checked[grid[i][j]]) {
				Delete(grid[i][j]);
				onGrid[grid[i][j]] = false;
			}
			
			// 처음 발견한 미생물이면 기록하고, 방문 처리
			else {
				checked[grid[i][j]] = true;
				GetArea(i, j, grid[i][j]);
			}
		}
	}
}

void CheckDead() {
	for (int v = 1; v <= q; v++) {
		if (!onGrid[v]) continue;
		if (viruses[v].size <= 0) onGrid[v] = false;
	}
}

void Drop(int turn) {
	onGrid[turn] = true;
	for (int v = 0; v < viruses[turn].area.size(); v++) {
		int ci, cj;
		tie(ci, cj) = viruses[turn].area[v];

		if (grid[n + 1 - cj][ci] != EMPTY) {
			viruses[grid[n + 1 - cj][ci]].size--;
		}
		grid[n + 1 - cj][ci] = turn;
	}

	CheckDead();
	CheckDividen();
}



void InitTempGrid() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			tempGrid[i][j] = EMPTY;
		}
	}
}

void DupGrid() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			grid[i][j] = tempGrid[i][j];
		}
	}
}

bool Fit(int i, int j, int id) {
	vector<pair<int, int>> nextArea;
	// x작은 순, y작은 순으로 정렬
	sort(viruses[id].area.begin(), viruses[id].area.end());

	// 이동량 기준치 설정
	int di = 0, dj = 0;
	for (int da = 0; da < viruses[id].area.size(); da++) {
		int ci = viruses[id].area[da].first, cj = viruses[id].area[da].second;
		if (grid[n + 1 - cj][ci] != id) continue;
		else {
			di = i - ci, dj = j - cj;
			break;
		}
	}

	for (int da = 0; da < viruses[id].area.size(); da++) {
		int ci = viruses[id].area[da].first, cj = viruses[id].area[da].second;
		// 옮길 때, 그리드에서도 실제 id인지 확인하고 옮겨야 함.
		if (grid[n + 1 - cj][ci] != id) continue;

		int ni = ci + di, nj = cj + dj;
		// 배양 용기 범위를 벗어나거나
		if (!InGrid(ni, nj)) return false;
		// 다른 미생물이 존재할 경우
		if (tempGrid[n + 1 - nj][ni] != EMPTY) return false;

		nextArea.push_back({ ni, nj });
	}

	// 전부 이동했을 경우 영역 갱신
	viruses[id].area = nextArea;

	return true;
}

bool FindSpace(int id) {
	// 최대한 x좌표가 작은 위치
	for (int i = 1; i <= n; i++) {
		// 최대한 y좌표가 작은 위치
		for (int j = 1; j <= n; j++) {
			// 자리를 찾았을 경우 영역 갱신까지
			if (Fit(i, j, id)) return true;
		}
	}

	return false;
}

void Deliver(int id) {
	for (int da = 0; da < viruses[id].area.size(); da++) {
		int ci = viruses[id].area[da].first, cj = viruses[id].area[da].second;

		tempGrid[n + 1 - cj][ci] = id;
	}
}

void Move() {
	InitTempGrid();
	vector<pair<int, int>> order;

	for (int v = 1; v <= q; v++) {
		// 그리드 상에 존재하는 미생물은 전부 옮김.
		if (!onGrid[v]) continue;

		order.push_back({ -viruses[v].size, v });
	}

	// 사이즈가 가장 큰 바이러스부터, 같으면 가장 먼저 투입된 미생물부터
	sort(order.begin(), order.end());

	for (int o = 0; o < order.size(); o++) {
		int curId = order[o].second;
		if (!FindSpace(curId)) onGrid[curId] = false;
		// tempGrid로 이동
		else Deliver(curId);
	}

	DupGrid();
}



void Record() {
	int curScore = 0;
	vector<bool> checked;
	checked.resize(q + 1, false);
	for (int v = 1; v <= q; v++) {
		if (!onGrid[v]) continue;

		checked[v] = true;
		vector<bool> curChecked;
		curChecked.resize(q + 1);

		for (int da = 0; da < viruses[v].area.size(); da++) {
			int ci = viruses[v].area[da].first, cj = viruses[v].area[da].second;

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

				int nearV = grid[n + 1 - nj][ni];
				if (!InGrid(ni, nj)) continue;
				if (nearV == EMPTY) continue;
				if (nearV == v) continue;

				if (!checked[nearV] && !curChecked[nearV]) {
					curScore += viruses[v].size * viruses[nearV].size;
					curChecked[nearV] = true;
				}
			}
		}
	}

	cout << curScore << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	Init();

	for (int turn = 1; turn <= q; turn++) {
		// 1. 미생물 투입
		Drop(turn); // 사이즈는 갱신되나, 상세 좌표는 갱신 X 상태.

		// 2. 배양 용기 이동
		Move();

		// 3. 실험 결과 기록
		Record();
	}

	return 0;
}