[백준][C++] 17135: 캐슬 디펜스

문제 링크: https://www.acmicpc.net/problem/17135

 

구현 문제입니다.

어렵지는 않은데 참 귀찮은 문제입니다

 

일단 궁수를 배치할 수 있는 위치 조합을 만들어냅니다. next_permutation이랑 0,1배열 적당히 써서 만들거나 재귀로 짜거나 암튼 조합을 만들면 됩니다.

그 다음부터는 그냥 적혀있는대로 구현하면 됩니다. 각 궁수 위치 조합마다 게임을 진행합니다.

 

게임의 턴은 다음과 같습니다. 각 궁수마다 가장 가까우면서 왼쪽에 있는 적 중에 거리가 D 이하인 녀석을 체크만 해둡니다. 지우지는 않습니다. 잡을 수 있는 적이 없으면 아무도 체크하지 않습니다.

각 궁수마다 잡을 녀석을 전부 체크했으면 체크한 적들을 지워줍니다.

그 다음 적 한마리씩 아래로 한칸 이동합니다. 성이 있는 칸으로 이동한 적은 뺍니다.

턴을 모든 적이 격자판에서 없어질 때까지 반복합니다

 

보통은 이런 문제 풀면서 행, 열 인덱스갖고 실수를 하는데 이번엔 이상한 실수를 했습니다. 그건 바로 적이 성이 있는 칸으로 이동하면 '게임이 끝난다'라고 가정하고 풀었는데 ;; 그랬더니 4번 예제가 이해가 안되는겁니다. 분명 어떻게 배치해도 3마리밖에 못잡고 끝나는데 15라니?

문제를 천천히 다시 읽어보니 '모든 적이 격자판에서 제외되면 게임이 끝난다'라는걸 앞 문장이랑 합쳐서 잘못 읽은거였습니다. 후우........

#pragma GCC optimize ("Ofast")

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int N, M, D;

constexpr int m_dist(int y1, int x1, int y2, int x2) {
	int diff_y = y2 - y1;
	if (diff_y < 0) diff_y = -diff_y;
	int diff_x = x2 - x1;
	if (diff_x < 0) diff_x = -diff_x;
	return diff_y + diff_x;
}

int defense(const vector<int>& archer, list<pair<int, int>> mobs) {
	int ret = 0;

	while (!mobs.empty()) {
		// 궁수마다 공격할거 정함
		set<pair<int, int>> targets;
		for (const auto& archer_col : archer) {
			int target_y=INF, target_x=INF, min_d=INF;

			for (const auto& [m_y, m_x] : mobs) {
				int dist = m_dist(N, archer_col, m_y, m_x);
				if (dist <= D && (dist < min_d || (dist == min_d && m_x < target_x))) {
					min_d = dist;
					target_y = m_y, target_x = m_x;
				}
			}

			if (min_d != INF)
				targets.emplace(target_y, target_x);
		}

		// 체크된거 지움
		for (const auto& [t_y, t_x] : targets) {
			for (auto it = mobs.begin(); it != mobs.end(); ) {
				const auto& [y, x] = *it;
				if (y==t_y && x==t_x) {
					mobs.erase(it);
					++ret;
					break;
				}

				++it;
			}
		}

		// 몹 1칸씩 이동
		for (auto it = mobs.begin(); it != mobs.end();) {
			auto& [m_y, m_x] = *it;
			++m_y;
			if (m_y == N)	// 성으로 이동 --> 제외
				it = mobs.erase(it);
			else
				++it;
		}
	}
	
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> N >> M >> D;
	list<pair<int, int>> mobs;	// y, x
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			int in; cin >> in;
			if (in)
				mobs.emplace_back(i, j);
		}
	}

	vector<int> archer_cols(M);
	for (int i=0; i<M; ++i)
		archer_cols[i] = i;

	vector<int> archer_mask(M);
	archer_mask[M-1] = archer_mask[M-2] = archer_mask[M-3] = 1;

	int mx = 0;
	do {
		vector<int> archer;

		for (int i=0; i<M; ++i)
			if (archer_mask[i])
				archer.push_back(archer_cols[i]);

		mx = max(mx, defense(archer, mobs));
	} while (next_permutation(archer_mask.begin(), archer_mask.end()));
	cout << mx << '\n';
	
	return 0;
}

재미도 감동도 배울점도 없는데 구현 시간은 좀 오래 걸리는 이런 문제는 개인적으로 너무 싫습니다