메두사와 전사들

BFS, Simulation

평균 : 180'

sol : 235' 27''

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

Learnings

• 두 번째 푸는데도 4시간 걸리는 미친 문제
• 주 병목은 부채꼴 진행

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

// 0-based
#define EMPTY 0
#define MAX_N 60
#define ROAD 0
#define NOT_ROAD 1

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3

int roadGrid[MAX_N][MAX_N];
int solderNumGrid[MAX_N][MAX_N];
pair<int, int> fromWhere[MAX_N][MAX_N];
bool bestVision[MAX_N][MAX_N];
vector<pair<int, int>> bestStunned;

int movedDist, stoneCnt, attackCnt;

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

int n, m;
struct Medusa {
	int si;
	int sj;
	int ei;
	int ej;
	pair<int, int> curPos;
	vector<pair<int, int>> path;

	Medusa() :
		si(-1), sj(-1), ei(-1), ej(-1), curPos({ -1, -1 }) {
	}
};

struct Solder {
	int i;
	int j;
	bool stone;
	bool onGrid;

	Solder() {};
};

Medusa medusa;
vector<Solder> solders;

void DebugVision(bool v[MAX_N][MAX_N]) {
	cout << endl << "VISION" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << v[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

void Debug() {
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (solderNumGrid[i][j] > 0) cout << "1 ";
			else if (i == medusa.curPos.first && j == medusa.curPos.second) cout << "M ";
			else cout << "0 ";
		}
		cout << endl;
	}
	cout << endl;
}

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

	cin >> medusa.si >> medusa.sj >> medusa.ei >> medusa.ej;

	solders.resize(m + 1);
	for (int s = 1; s <= m; s++) {
		int ai, aj;
		cin >> ai >> aj;
		solders[s].i = ai;
		solders[s].j = aj;
		solders[s].stone = false;
		solders[s].onGrid = true;
		solderNumGrid[ai][aj]++;
	}

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

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

void InitFromWhere() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			fromWhere[i][j] = { -1, -1 };
		}
	}
}

void InitBestVision() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			bestVision[i][j] = false;
		}
	}
}

bool GetMedusaPath() {
	bool possible = false;
	InitFromWhere();

	queue<pair<int, int>> q;
	q.push({ medusa.si, medusa.sj });
	fromWhere[medusa.si][medusa.sj] = { medusa.si, medusa.sj };

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

		if (ci == medusa.ei && cj == medusa.ej) {
			possible = true;
			break;
		}

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

			if (!InGrid(ni, nj)) continue;
			if (fromWhere[ni][nj] != make_pair(-1, -1)) continue;
			if (roadGrid[ni][nj] == NOT_ROAD) continue;

			fromWhere[ni][nj] = { ci, cj };
			q.push({ ni, nj });
		}
	}

	if (!possible) return false;

	vector<pair<int, int>> reversePath;
	pair<int, int > curPos = { medusa.ei, medusa.ej };

	while (curPos != make_pair(medusa.si, medusa.sj)) {
		reversePath.push_back(curPos);
		curPos = fromWhere[curPos.first][curPos.second];
	}

	medusa.path.push_back({ medusa.si, medusa.sj });
	for (int i = reversePath.size() - 1; i >= 0; i--) {
		medusa.path.push_back(reversePath[i]);
	}

	return true;
}

int Oppos(int dir) {
	if (dir == UP) return DOWN;
	if (dir == DOWN) return UP;
	if (dir == LEFT) return RIGHT;
	if (dir == RIGHT) return LEFT;
}

void GetBestDir() {
	int bestCnt = 0;
	InitBestVision();

	// 상,하,좌,우 순으로 바라볼 때
	for (int curD = 0; curD < 4; curD++) {
		// 위치, 방향
		queue<tuple<int, int, int, int>> caught;

		bool visited[MAX_N][MAX_N];
		bool vision[MAX_N][MAX_N];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				visited[i][j] = false;
				vision[i][j] = false;
			}
		}
		
		// Phase 1. 전사 탐색
		queue<tuple<int, int, int, int>> q;
		int ci, cj;
		tie(ci, cj) = medusa.curPos;
		for (int sightD = 0; sightD < 4; sightD++) {
			if (sightD == Oppos(curD)) continue;
			int ni, nj;
			if (sightD == curD) {
				ni = ci + ds[sightD][0], nj = cj + ds[sightD][1];
			}
			else {
				ni = ci + ds[sightD][0] + ds[curD][0], nj = cj + ds[sightD][1] + ds[curD][1];
			}

			if (!InGrid(ni, nj)) continue;
			if (visited[ni][nj]) continue;
			visited[ni][nj] = true,	vision[ni][nj] = true;
			q.push(make_tuple(ni, nj, sightD, curD));
			if (solderNumGrid[ni][nj] > 0) caught.push(make_tuple(ni, nj, sightD, curD));
		}

		

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

			// 직선인 경우
			if (sightD == curD) {
				int ni = ci + ds[sightD][0], nj = cj + ds[sightD][1];
				if (!InGrid(ni, nj)) continue;
				if (visited[ni][nj]) continue;
				visited[ni][nj] = true, vision[ni][nj] = true;
				
				q.push({ ni, nj, sightD, curD });
				if (solderNumGrid[ni][nj] > 0) caught.push(make_tuple(ni, nj, sightD, curD));
			}
			// 대각인 경우
			else {
				int ni1 = ci + ds[curD][0], nj1 = cj + ds[curD][1];
				int ni2 = ni1 + ds[sightD][0], nj2 = nj1 + ds[sightD][1];
				
				if (InGrid(ni1, nj1) && !visited[ni1][nj1]) {
					q.push({ ni1, nj1, sightD, curD });
					visited[ni1][nj1] = true;
					vision[ni1][nj1] = true;
					if (solderNumGrid[ni1][nj1] > 0)	caught.push({ ni1, nj1, sightD, curD });
				}
				if (InGrid(ni2, nj2) && !visited[ni2][nj2]) {
					q.push({ ni2, nj2, sightD, curD });
					visited[ni2][nj2] = true;
					vision[ni2][nj2] = true;
					if (solderNumGrid[ni2][nj2] > 0)	caught.push({ ni2, nj2, sightD, curD });
				}
			}
		}

		// Phase 2. 전사 위치에서 다시 끄기
		vector<pair<int, int>> stunned;
		while (!caught.empty()) {
			int i, j, sightD, curD;
			tie(i, j, sightD, curD) = caught.front();

			caught.pop();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					visited[i][j] = false;
				}
			}

			// 뒤에 가려진 전사
			if (!vision[i][j]) continue;

			// 실제로 굳은 전사들의 위치
			stunned.push_back({ i, j });

			// 직선 방향인 경우
			if (sightD == curD) {
				int ci = i, cj = j;
				while (InGrid(ci, cj)) {
					ci += ds[sightD][0], cj += ds[sightD][1];
					vision[ci][cj] = false;
				}
				continue;
			}

			// 대각 방향인 경우
			queue<pair<int, int>> sq;
			sq.push({ i, j });
			visited[i][j] = true;

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

				int	ni1 = ci + ds[curD][0], nj1 = cj + ds[curD][1];
				int ni2 = ni1 + ds[sightD][0], nj2 = nj1 + ds[sightD][1];

				if (InGrid(ni1, nj1) && !visited[ni1][nj1]) {
					sq.push({ ni1, nj1 });
					visited[ni1][nj1] = true;
					vision[ni1][nj1] = false;
				}
				if (InGrid(ni2, nj2) && !visited[ni2][nj2]) {
					sq.push({ ni2, nj2 });
					visited[ni2][nj2] = true;
					vision[ni2][nj2] = false;
				}
			}
		}

		int curCnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (vision[i][j]) {
					curCnt += solderNumGrid[i][j];
				}
			}
		}

		if (curCnt > bestCnt) {
			bestCnt = curCnt;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					bestVision[i][j] = vision[i][j];
				}
			}
			bestStunned = stunned;
		}
	}
}

void Stun() {
	for (int a = 0; a < bestStunned.size(); a++) {
		for (int s = 1; s <= m; s++) {
			if (!solders[s].onGrid) continue;
			if (solders[s].i == bestStunned[a].first && solders[s].j == bestStunned[a].second) {
				solders[s].stone = true;
				stoneCnt++;
			}
		}
	}
}

int Dist(int si, int sj) {
	int mi, mj;
	tie(mi, mj) = medusa.curPos;

	return abs(si - mi) + abs(sj - mj);
}

void SoldersMove() {
	for (int s = 1; s <= m; s++) {
		if (!solders[s].onGrid) continue;
		if (solders[s].stone) {
			solders[s].stone = false;
			continue;
		}

		int ci = solders[s].i, cj = solders[s].j;
		int minDist = Dist(ci, cj);
		int best_i = -1, best_j = -1;
		// 1st move
		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];
			if (!InGrid(ni, nj)) continue;
			if (bestVision[ni][nj]) continue;
			if (Dist(ni, nj) >= minDist) continue;

			minDist = Dist(ni, nj);
			best_i = ni, best_j = nj;
		}

		if (best_i == -1) continue;
		solderNumGrid[solders[s].i][solders[s].j]--;
		solders[s].i = best_i, solders[s].j = best_j;
		solderNumGrid[solders[s].i][solders[s].j]++;
		movedDist++;

		// check
		if (solders[s].i == medusa.curPos.first && solders[s].j == medusa.curPos.second) {
			attackCnt++;
			solders[s].onGrid = false;
			solderNumGrid[solders[s].i][solders[s].j]--;
			continue;
		}

		// 2nd move
		int tempDs[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
		ci = solders[s].i, cj = solders[s].j;
		minDist = Dist(ci, cj);
		best_i = -1, best_j = -1;
		for (int d = 0; d < 4; d++) {
			int ni = ci + tempDs[d][0], nj = cj + tempDs[d][1];
			if (!InGrid(ni, nj)) continue;
			if (bestVision[ni][nj]) continue;
			if (Dist(ni, nj) >= minDist) continue;

			minDist = Dist(ni, nj);
			best_i = ni, best_j = nj;
		}

		if (best_i == -1) continue;
		solderNumGrid[solders[s].i][solders[s].j]--;
		solders[s].i = best_i, solders[s].j = best_j;
		solderNumGrid[solders[s].i][solders[s].j]++;
		movedDist++;

		// check
		if (solders[s].i == medusa.curPos.first && solders[s].j == medusa.curPos.second) {
			attackCnt++;
			solders[s].onGrid = false;
			solderNumGrid[solders[s].i][solders[s].j]--;
		}
	}
}

void MedusaMove(int t) {
	medusa.curPos = medusa.path[t];
	int ci, cj;
	tie(ci, cj) = medusa.curPos;
	if (solderNumGrid[ci][cj] > 0) {
		solderNumGrid[ci][cj] = 0;
		for (int s = 1; s <= m; s++) {
			if (!solders[s].onGrid) continue;
			if (solders[s].i == ci && solders[s].j == cj) {
				solders[s].onGrid = false;
			}
		}
	}
}

int main() {
	Init();

	if (!GetMedusaPath()) {
		cout << -1;
		return 0;
	}

	medusa.curPos = medusa.path[0];
	for (int t = 1; t < medusa.path.size() - 1; t++) {
		movedDist = 0, attackCnt = 0, stoneCnt = 0;
		
		MedusaMove(t);

		GetBestDir();

		Stun();

		SoldersMove();

		cout << movedDist << ' ' << stoneCnt << ' ' << attackCnt << '\n';
	}
	cout << 0;

	return 0;
}