(BOJ) 17135 캐슬 디펜스

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

 

문제 설명:

n*m 크기의 격자판 안에 적이 존재 (칸당 적은 최대 한 명)

궁수는 3명 존재 n*m 격자판 밑에 줄에 존재 가능

궁수는 동시에 공격하고, 가장 가까운 위치에서 가장 왼쪽에 있는 적을 공격한다.

궁수들의 공격이 끝나면 적들은 한 칸씩 밑으로 이동한다.

적들은 궁수들이 있는 줄에 도달하면 소멸된다.

이 때, 궁수들이 공격으로 제거할 수 있는 적의 최대 수는?

 

문제 풀이:

1. n번째 줄에 궁수들을 각 각 어디에 놓을지 3중 포문을 통해 결정 -> mC3

2. 궁수들을 배치 후 적들의 위치와 공격 거리 제한을 고려하여 공격 가능한 적 결정

    (모든 궁수들을 한번에 돌리고 겹치지 않는 적들 수만 카운트)

    ㄴ visit 배열을 만들어 겹치는지 판단

3. 적 한칸씩 내려옴 -> day++로 처리

4. 적 전부 사라질 때까지 2, 3 반복

 

 

소스 코드:

typedef pair<int, int> P;
int n, m, d,res,sz,rest;
bool visit[16][16];

vector<P> v;
P finding(int y, int day) {
	int dist = 15 * 15;
	P pos = make_pair(15, 15);
	for (int i = 0; i < v.size(); i++) {
		int xx = v[i].first, yy = v[i].second;
		if (xx + day >= n) {
			if(!visit[xx][yy])rest--;
			visit[xx][yy] = true;
			continue;
		}
		int t = abs(n - (xx + day)) + abs(y - yy);
		if (t <= d&& !visit[xx][yy]) {
			if (dist > t) {
				dist = t;
				pos = make_pair(xx + day, yy);
			}
			else if (dist == t && pos.second > yy) pos = make_pair(xx + day, yy);
		}
	}
	return pos;
}
void func(int a,int b,int c) {
	memset(visit, false, sizeof(visit));
	rest = sz;
	int cnt = 0;
	int day = 0;
	while (1) {
		P tmp=finding(a, day);
		P tmp2 = finding(b, day);
		P tmp3 = finding(c, day);
		if (tmp!=make_pair(15,15)&&!visit[tmp.first-day][tmp.second]) {
			visit[tmp.first-day][tmp.second] = true;
			rest--;
			cnt++;
		}
		if (tmp2 != make_pair(15, 15)&&!visit[tmp2.first-day][tmp2.second]) {
			visit[tmp2.first-day][tmp2.second] = true;
			rest--;
			cnt++;
		}
		if (tmp3!= make_pair(15, 15)&&!visit[tmp3.first-day][tmp3.second]) {
			visit[tmp3.first-day][tmp3.second] = true;
			rest--;
			cnt++;
		}
		if (rest>0) day++;
		else break;
	}
	res = max(cnt, res);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int a;
			cin >> a;
			if (a == 1) {
				v.push_back({ i,j });
			}
		}
	}
	sz = v.size();

	for (int i = 0; i < m; i++) {
		for (int j = i + 1; j < m; j++) {
			for (int k = j + 1; k < m; k++) {
				func(i, j, k);
			}
		}
	}
	cout << res << '\n';
	
	return 0;

}