메두사와 전사들

Simulation, BFS

• 평균 : 180'

---

sol : 311' 33''

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

Learnings

• 시야 기능을 설계할 때, 자료구조 '큐'의 본질적인 기능을 자유롭게 활용할 수 있었다면 시간을 크게 줄일 수 있었을 것.
• 메두사의 시선을 상하좌우에 맞춰 대각으로 뻗어나가는 BFS는 잘했는데, 처음으로 발견한 전사들을 기준으로 시야를 다시 꺼주는 과정에서 Queue의 본질적인 기능을 망각하고 있었다.
• 말 그대로 First in First out의 기능을 가진 Queue + 최단 거리를 보장하는 BFS. 이렇게 두 기능이 합쳐지면서 메두사 시야와 이로 인해 가려지는 범위를 쉽게 구할 수 있는 것.
• 아주 재밌는 문제였다!!

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

#define MAX_N 50
#define ROAD 0
#define NOT_ROAD 1
#define MEDUSA 2
#define PARK 3

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
#define LU 4
#define LD 5
#define RU 6
#define RD 7

// visible 맵 규칙
#define UNKNOWN 0
#define VISIBLE 1
#define NOT_VISIBLE 2
#define MESUDA 3

#define NOT_BLOCKED false
#define BLOCKED true

using namespace std;

int n, m, turn;
bool parkReachable = false;   // 수정: 반드시 초기화
// 상, 하, 좌, 우
int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int roadGrid[MAX_N][MAX_N];
pair<int, int> fromWhere[MAX_N][MAX_N];

bool visited[MAX_N][MAX_N];
int visible[MAX_N][MAX_N];
int solderNumGrid[MAX_N][MAX_N];

struct Solder {
	int i;
	int j;
	int movedDist;
	bool stunned;
	bool isDead;
	int attackTurn;

	Solder() {}
	Solder(int _i, int _j, int _movedDist, bool _stunned, bool _isDead, int _attackTurn) :
		i(_i), j(_j), movedDist(_movedDist), stunned(_stunned), isDead(_isDead), attackTurn(_attackTurn) {
	}
};

struct Medusa {
	int i;
	int j;
	vector<pair<int, int>> path;

	Medusa() {}
	Medusa(int _i, int _j) :
		i(_i), j(_j) {
	}
};

vector<Solder> solders;

Medusa medusa;
pair<int, int> park;

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

void DebugVisible() {
	cout << endl << "DEBUG VISIBLE" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << visible[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void DebugSolderNumGrid() {
	cout << endl << "DEBUG SOLDER NUM GRID" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << solderNumGrid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

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

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

void InitVisible() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visible[i][j] = UNKNOWN;
		}
	}
}

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

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

	int sr, sc, er, ec;
	cin >> sr >> sc >> er >> ec;
	medusa = Medusa(sr, sc);

	solders.resize(m + 1);
	for (int i = 1; i <= m; i++) {
		int ar, ac;
		cin >> ar >> ac;
		solders[i] = Solder(ar, ac, 0, false, false, -1);
		solderNumGrid[ar][ac]++;
	}

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

	roadGrid[er][ec] = PARK;
	park = make_pair(er, ec);
}

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

void GetMedusaPath() {
	InitFromWhere();
	queue<pair<int, int>> q;

	q.push({ medusa.i, medusa.j });
	fromWhere[medusa.i][medusa.j] = { medusa.i, medusa.j };

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

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

			if (InGrid(ni, nj) && fromWhere[ni][nj].first == -1) {
				if (roadGrid[ni][nj] == ROAD) {
					fromWhere[ni][nj] = { ci, cj };
					q.push({ ni, nj });
				}
				else if (roadGrid[ni][nj] == PARK) {
					fromWhere[ni][nj] = { ci, cj };
					parkReachable = true;
					break;
				}
			}
		}
		if (parkReachable) break;
	}

	if (!parkReachable) return;

	int ci = park.first, cj = park.second;
	while (ci != medusa.i || cj != medusa.j) {
		medusa.path.push_back({ ci, cj });
		tie(ci, cj) = fromWhere[ci][cj];
	}
}

void MedusaMove() {
	int ci, cj;
	tie(ci, cj) = medusa.path[medusa.path.size() - 1];
	medusa.path.pop_back();

	medusa.i = ci, medusa.j = cj;
	for (int s = 1; s <= m; s++) {
		if (solders[s].isDead) continue;   // 수정
		if (solders[s].i == medusa.i && solders[s].j == medusa.j) {
			solderNumGrid[solders[s].i][solders[s].j]--;   // 수정: grid에서도 제거
			solders[s].isDead = true;
		}
	}
}

bool IsMedusaArrived() {
	if (medusa.i == park.first && medusa.j == park.second) return true;
	return false;
}

/////////////////////////////////////////////////////////////////////////////////
void InitState() {
	for (int s = 1; s <= m; s++) {
		solders[s].movedDist = 0;
		solders[s].stunned = false;
	}
}

int OppoD(int d) {
	if (d == UP) return DOWN;
	if (d == DOWN) return UP;
	if (d == LEFT) return RIGHT;
	return LEFT;
}

pair<int, int> GetSideD(int curD) {
	if (curD == UP || curD == DOWN) {
		return { LEFT, RIGHT };
	}
	return { UP, DOWN };
}

void VisionOperation(int curD) {
	InitVisited();
	queue<pair<int, int>> q;
	q.push({ medusa.i, medusa.j });
	visited[medusa.i][medusa.j] = true;

	queue<tuple<int, int, int, int>> caughtSolder;

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

		// 직각
		int ni = ci + ds[curD][0], nj = cj + ds[curD][1];
		if (InGrid(ni, nj) && !visited[ni][nj]) {
			visited[ni][nj] = true;
			visible[ni][nj] = VISIBLE;
			q.push({ ni, nj });
			if (solderNumGrid[ni][nj] > 0) {
				caughtSolder.push({ ni, nj, curD, curD });
			}
		}
	}

	pair<int, int> sideD = GetSideD(curD);

	q.push({ medusa.i, medusa.j });
	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		// 대각1
		int ni = ci + ds[sideD.first][0] + ds[curD][0], nj = cj + ds[sideD.first][1] + ds[curD][1];
		int ni2 = ci + ds[curD][0], nj2 = cj + ds[curD][1];

		if (InGrid(ni, nj) && !visited[ni][nj]) {
			visited[ni][nj] = true;
			visible[ni][nj] = VISIBLE;
			q.push({ ni, nj });

			if (solderNumGrid[ni][nj] > 0) {
				caughtSolder.push({ ni, nj, sideD.first, curD });
			}
		}

		if (InGrid(ni2, nj2) && !visited[ni2][nj2]) {
			visited[ni2][nj2] = true;
			visible[ni2][nj2] = VISIBLE;
			q.push({ ni2, nj2 });

			if (solderNumGrid[ni2][nj2] > 0) {
				caughtSolder.push({ ni2, nj2, sideD.first, curD });
			}
		}
	}

	q.push({ medusa.i, medusa.j });
	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		// 대각2
		int ni = ci + ds[sideD.second][0] + ds[curD][0], nj = cj + ds[sideD.second][1] + ds[curD][1];
		int ni2 = ci + ds[curD][0], nj2 = cj + ds[curD][1];

		if (InGrid(ni, nj) && !visited[ni][nj]) {
			visited[ni][nj] = true;
			visible[ni][nj] = VISIBLE;
			q.push({ ni, nj });

			if (solderNumGrid[ni][nj] > 0) {
				caughtSolder.push({ ni, nj, sideD.second, curD });
			}
		}

		if (InGrid(ni2, nj2) && !visited[ni2][nj2]) {
			visited[ni2][nj2] = true;
			visible[ni2][nj2] = VISIBLE;
			q.push({ ni2, nj2 });

			if (solderNumGrid[ni2][nj2] > 0) {
				caughtSolder.push({ ni2, nj2, sideD.second, curD });
			}
		}
	}

	InitVisited();
	while (!caughtSolder.empty()) {
		int si, sj;
		int sideDir, orthD;
		tie(si, sj, sideDir, orthD) = caughtSolder.front();
		caughtSolder.pop();

		queue<pair<int, int>> sq;
		sq.push({ si, sj });
		visited[si][sj] = true;

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

				int ni = ci + ds[sideDir][0], nj = cj + ds[sideDir][1];
				if (InGrid(ni, nj) && !visited[ni][nj]) {
					visited[ni][nj] = true;
					visible[ni][nj] = NOT_VISIBLE;
					sq.push({ ni, nj });
				}
			}
		}
		else {
			while (!sq.empty()) {
				int ci, cj;
				tie(ci, cj) = sq.front();
				sq.pop();

				// 대각
				int ni = ci + ds[sideDir][0] + ds[orthD][0], nj = cj + ds[sideDir][1] + ds[orthD][1];
				// 직각
				int ni2 = ci + ds[orthD][0], nj2 = cj + ds[orthD][1];
				if (InGrid(ni, nj) && !visited[ni][nj]) {
					visited[ni][nj] = true;
					visible[ni][nj] = NOT_VISIBLE;
					sq.push({ ni, nj });
				}
				if (InGrid(ni2, nj2) && !visited[ni2][nj2]) {
					visited[ni2][nj2] = true;
					visible[ni2][nj2] = NOT_VISIBLE;
					sq.push({ ni2, nj2 });
				}
			}
		}
	}
}

int CountStunnedSolder() {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visible[i][j] == VISIBLE) {
				cnt += solderNumGrid[i][j];
			}
		}
	}
	return cnt;
}

int SightTest(int curD) {
	InitVisible();
	VisionOperation(curD);
	return CountStunnedSolder();
}

void StunSolders() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visible[i][j] == VISIBLE && solderNumGrid[i][j] > 0) {
				for (int s = 1; s <= m; s++) {
					if (solders[s].isDead) continue;   // 수정
					if (solders[s].i == i && solders[s].j == j) {
						solders[s].stunned = true;
					}
				}
			}
		}
	}
}

void MedusaSight() {
	// 1. 각 방향별 전사 수 카운트
	int maxS = -1;    // 수정
	int maxD = UP;    // 수정

	for (int d = UP; d <= RIGHT; d++) {
		int curS = SightTest(d);
		if (curS > maxS) {
			maxS = curS;
			maxD = d;
		}
	}

	// 2. 해당 방향으로 시선 적용
	InitVisible();
	VisionOperation(maxD);
	StunSolders();
}

int Dist(int from_i, int from_j, int to_i, int to_j) {
	return abs(from_i - to_i) + abs(from_j - to_j);
}

void SoldersMove() {
	for (int s = 1; s <= m; s++) {
		if (solders[s].stunned || solders[s].isDead) continue;

		// 첫 번째 이동
		int initDist = Dist(solders[s].i, solders[s].j, medusa.i, medusa.j);
		int nextDist = Dist(solders[s].i, solders[s].j, medusa.i, medusa.j);
		int minD = -1;

		for (int d = UP; d <= RIGHT; d++) {
			int ni = solders[s].i + ds[d][0], nj = solders[s].j + ds[d][1];

			if (InGrid(ni, nj) && visible[ni][nj] != VISIBLE) {
				int curDist = Dist(ni, nj, medusa.i, medusa.j);
				if (curDist < nextDist) {
					nextDist = curDist;
					minD = d;
				}
			}
		}

		if (minD == -1) continue;

		solderNumGrid[solders[s].i][solders[s].j]--;
		solders[s].i = solders[s].i + ds[minD][0], solders[s].j = solders[s].j + ds[minD][1];
		solders[s].movedDist += (initDist - nextDist);
		solderNumGrid[solders[s].i][solders[s].j]++;

		// 두 번째 이동
		initDist = nextDist;
		minD = -1;
		for (int d = LEFT; d <= RIGHT; d++) {
			int ni = solders[s].i + ds[d][0], nj = solders[s].j + ds[d][1];

			if (InGrid(ni, nj) && visible[ni][nj] != VISIBLE) {
				int curDist = Dist(ni, nj, medusa.i, medusa.j);
				if (curDist < nextDist) {
					nextDist = curDist;
					minD = d;
				}
			}
		}
		for (int d = UP; d <= DOWN; d++) {
			int ni = solders[s].i + ds[d][0], nj = solders[s].j + ds[d][1];

			if (InGrid(ni, nj) && visible[ni][nj] != VISIBLE) {
				int curDist = Dist(ni, nj, medusa.i, medusa.j);
				if (curDist < nextDist) {
					nextDist = curDist;
					minD = d;
				}
			}
		}

		if (minD == -1) continue;

		solderNumGrid[solders[s].i][solders[s].j]--;
		solders[s].i = solders[s].i + ds[minD][0], solders[s].j = solders[s].j + ds[minD][1];
		solders[s].movedDist += (initDist - nextDist);
		solderNumGrid[solders[s].i][solders[s].j]++;
	}
}

void SoldersAttack() {
	for (int s = 1; s <= m; s++) {
		if (solders[s].isDead) continue;

		if (solders[s].i == medusa.i && solders[s].j == medusa.j) {
			solderNumGrid[solders[s].i][solders[s].j]--;   // 유지/필수
			solders[s].isDead = true;
			solders[s].attackTurn = turn;
		}
	}
}

void PrintCurState() {
	int distSum = 0, stoneNum = 0, attackedSoldersNm = 0;

	for (int s = 1; s <= m; s++) {
		// 1. 해당 턴 전사들의 이동 거리 합
		distSum += solders[s].movedDist;

		// 2. 돌이 된 전사 수
		if (solders[s].stunned) stoneNum++;

		// 3. 메두사를 공격한 전사의 수
		if (solders[s].attackTurn == turn) attackedSoldersNm++;
	}

	cout << distSum << " " << stoneNum << " " << attackedSoldersNm << endl;
}

int main() {
	Init();

	// 0. 메두사 이동 경로 전처리 (만약 경로가 없을 경우 -1 출력)
	GetMedusaPath();

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

	while (true) {
		turn++;

		// 0. initializer
		InitState();

		// 1. 메두사의 이동
		MedusaMove();

		// 2. 메두사 도착 여부 확인
		if (IsMedusaArrived()) break;

		// 3. 메두사의 시선
		MedusaSight();

		// 4. 전사들의 이동
		SoldersMove();

		// 5. 전사의 공격
		SoldersAttack();

		PrintCurState();
	}

	cout << 0;

	return 0;
}