왕실의 기사 대결

Simulation

평균 : 180'

---

sol : 190' 26''

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

Learnings

• 너무 어렵게 풀었다. 직사각형의 좌표들을 전부 갖고 움직일 필요 없이, 직사각형의 겹침 여부를 중점으로 짰다면 훨씬 쉽게 풀 수 있었을 것.
• 재귀에 너무 두려워하지 말자.

[모범답안 연쇄 충돌 판정 알고리즘]
bool dfs_knight(int idx, int direction) {
    visited[idx] = true;

    if (!knights[idx].can_move(direction)) {
        return false;
    }

    for (int next_idx = 0; next_idx < n; ++next_idx) {
        if (idx == next_idx || !knights[next_idx].is_alive() || visited[next_idx]) continue;

        if (knights[next_idx].is_pushed(knights[idx], direction)) {
            if (!dfs_knight(next_idx, direction)) {
                return false;
            }
        }
    }
  
    return true;
}

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <unordered_map>
#include <stack>
#include <set>

using namespace std;

#define MAX_L 45
#define EMPTY 0
#define TRAP 1 
#define WALL 2

int l, n, q;
int chessGrid[MAX_L][MAX_L];
int knightGrid[MAX_L][MAX_L];
// 상, 우, 하, 좌
int ds[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
vector<pair<int, int>> order;


// 영역, 체력, 누적 데미지, 생존 여부
struct Knight {
	vector<pair<int, int>> area;
	int k;
	int damageSum;
	bool isChosen;
	bool isPushed;
	bool isAlive;

	Knight() {}

	Knight(vector<pair<int, int>> _area, int _k, int _damageSum, bool _isChosen, bool _isPushed, bool _isAlive) :
		area(_area), k(_k), damageSum(_damageSum), isChosen(_isChosen), isPushed(_isPushed), isAlive(_isAlive) {
	}
};

vector<Knight> knights;

void DrawChessGrid() {
	cout << endl << "Chess Grid DEBUG" << endl;
	for (int r = 0; r <= l + 1; r++) {
		for (int c = 0; c <= l + 1; c++) {
			cout << chessGrid[r][c] << ' ';
		}
		cout << endl;
	}
	cout << "Chess Grid DEBUG FIN" << endl;
}

void DrawKnightGrid() {
	cout << endl << "Knight Grid DEBUG" << endl;
	for (int r = 1; r <= l; r++) {
		for (int c = 1; c <= l; c++) {
			cout << knightGrid[r][c] << ' ';
		}
		cout << endl;
	}
	cout << "Knight Grid DEBUG FIN" << endl;
}

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

	knights.resize(n + 1);
	order.resize(q + 1);

	// 테두리 벽화 작업
	for (int i = 0; i <= l + 1; i++) {
		chessGrid[i][0] = WALL;
		chessGrid[i][l + 1] = WALL;
	}

	// 테두리 벽화 작업
	for (int j = 0; j <= l + 1; j++) {
		chessGrid[0][j] = WALL;
		chessGrid[l + 1][j] = WALL;
	}

	for (int r = 1; r <= l; r++) {
		for (int c = 1; c <= l; c++) {
			cin >> chessGrid[r][c];
		}
	}

	for (int i = 1; i <= n; i++) {
		int ir, ic, ih, iw, ik;
		cin >> ir >> ic >> ih >> iw >> ik;
		vector<pair<int, int>> area;
		for (int sr = ir; sr < ir + ih; sr++) {
			for (int sc = ic; sc < ic + iw; sc++) {
				area.push_back(make_pair(sr, sc));
				knightGrid[sr][sc] = i;
			}
		}
		knights[i] = Knight(area, ik, 0, false, false, true);
	}

	for (int i = 1; i <= q; i++) {
		int id, dir;
		cin >> id >> dir;
		order[i] = make_pair(id, dir);
	}
}

bool KnightMove(int turn) {
	// 체스판에서 사라진 기사에게 명령을 내리면 아무런 반응이 없다.
	if (!knights[order[turn].first].isAlive) return false;

	// 공격이 성공했는가?
	bool attackSuccessed = true;

	// 해당 턴의 방향 설정
	int direction = order[turn].second;

	// 밀쳐진 기사들의 번호별 영역 저장 벡터
	unordered_map<int, vector<pair<int, int>>> movedKnightArea;

	// 밀쳐진 기사들의 번호 저장 벡터
	set<int> movedKnight;

	// 나중에 draw할 때 먼 곳부터 그리기 위한 stack 번호 저장 벡터
	stack<int> movedKnightOrder;

	// 민 기사부터 시작
	movedKnight.insert(order[turn].first);
	movedKnightOrder.push(order[turn].first);

	// 밀쳐진 기사와 구분하기 위한 isChosen true 설정.
	knights[order[turn].first].isChosen = true;

	while (!movedKnight.empty()) {
		int curKnightId = *movedKnight.begin();
		movedKnight.erase(*movedKnight.begin());

		// 이동된 기사로 처리
		knights[curKnightId].isPushed = true;

		for (int da = 0; da < knights[curKnightId].area.size(); da++) {
			int cdar, cdac, ndar, ndac;
			tie(cdar, cdac) = knights[curKnightId].area[da];
			ndar = cdar + ds[direction][0], ndac = cdac + ds[direction][1];

			// 만약 이동 후 위치에 벽이 있을 경우, false 반환.
			if (chessGrid[ndar][ndac] == WALL) {
				attackSuccessed = false;
				return attackSuccessed;
			}

			// 이동 후 영역 저장
			movedKnightArea[curKnightId].push_back(make_pair(ndar, ndac));

			// 만약 이동 후 위치에 다른 생존한 기사가 있을 경우
			if (knightGrid[ndar][ndac] != curKnightId && knightGrid[ndar][ndac] > 0) {
				movedKnight.insert(knightGrid[ndar][ndac]);
				movedKnightOrder.push(knightGrid[ndar][ndac]);
			}
		}
	}

	// 전부 벽에 만나지 않고 이동에 성공했을 경우
	while (!movedKnightOrder.empty()) {
		int curId = movedKnightOrder.top();
		movedKnightOrder.pop();

		// 기존 위치 삭제 후
		for (int i = 0; i < knights[curId].area.size(); i++) {
			knightGrid[knights[curId].area[i].first][knights[curId].area[i].second] = EMPTY;
		}

		// 현재 위치 draw
		for (int i = 0; i < movedKnightArea[curId].size(); i++) {
			knightGrid[movedKnightArea[curId][i].first][movedKnightArea[curId][i].second] = curId;
		}

		// Knight area도 업데이트
		knights[curId].area = movedKnightArea[curId];
	}

	return attackSuccessed;
}

void RemoveDeadKnight(int id) {
	// 사망 처리
	knights[id].isAlive = false;

	// 기사맵에서 삭제
	for (int i = 0; i < knights[id].area.size(); i++) {
		knightGrid[knights[id].area[i].first][knights[id].area[i].second] = EMPTY;
	}
}

void DamageControl() {
	for (int i = 1; i <= n; i++) {
		// 사라진 기사는 패스
		if (!knights[i].isAlive) continue;
		// 민 기사인 경우도 패스
		if (knights[i].isChosen) continue;

		// 밀쳐진 기사인 경우
		if (knights[i].isPushed) {
			for (int da = 0; da < knights[i].area.size(); da++) {
				int di, dj;
				tie(di, dj) = knights[i].area[da];

				// 함정이 있을 경우
				if (chessGrid[di][dj] == TRAP) {
					// 이번 데미지로 인해 현재 체력 이상의 대미지를 받을 경우
					if (knights[i].damageSum + 1 == knights[i].k) {
						RemoveDeadKnight(i);
						break;
					}
					else {
						knights[i].damageSum++;
					}
				}
			}
		}
	}
}

void ResetStatus() {
	for (int i = 1; i <= n; i++) {
		if (!knights[i].isAlive) continue;

		knights[i].isChosen = false;
		knights[i].isPushed = false;
	}
}

void PrintAnswer() {
	int answer = 0;
	for (int i = 1; i <= n; i++) {
		if (knights[i].isAlive) {
			answer += knights[i].damageSum;
		}
	}

	cout << answer;
}

int main() {
	Init();

	for (int turn = 1; turn <= q; turn++) {
		// 1. 기사 이동
		if (KnightMove(turn)) {
			// 2. 대결
			DamageControl();
		}

		// 3. 상태 초기화
		ResetStatus();
	}

	PrintAnswer();

	return 0;
}