백준 17135 C++

백준 17135

dfs로 총 3개의 궁수를 성벽에(y값 N) 배치한 이후, 그 조건에 따라 일일히 시뮬레이션을 하면 되는 문제다. 고민할 점은, 거리 계산과 왼쪽 우선 판정.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int N, M, D;


struct info {
	int y, x;
};

int map[15][15];

int mmap[15][15];
bool visited[15];
info archur[3];
info archurTarget[3];

int ans = -1;
int calDistance(info a, info b) {
	return (abs(a.y - b.y) + abs(a.x - b.x));
}

bool calLeft(info a, info b) {
	if (a.x < b.x) return false;
	return true;
}

int attack() {

	int enemy = 0;

	for (int i = 0; i < 3; i++) {
		int ny = archur[i].y;
		int nx = archur[i].x;

		info target = { 987654321,0 };
		int distance = D + 1;
		for (int y = 0; y < N; ++y) {
			for (int x = 0; x < M; ++x) {
				
				//0(적 없으면) 패스. 
				if (!mmap[y][x]) continue;
				info targetPos = { y,x };

				int distToEnemy = calDistance(archur[i], targetPos);
				//D가 최대점이니까, D보다 같거나 적을 때. 갱신. 
				if (distToEnemy < distance) {
					distance = calDistance(archur[i], targetPos);
					target = targetPos;
				}
				else if (distToEnemy == distance) {//만약 기존에 타겟으로 잡았던 것과 거리가 같은 경우에
					if (targetPos.x < target.x) {
						target = targetPos;
					}
				}
			}
		}
		archurTarget[i] = target;
	}


	for (int i = 0; i < 3; ++i) {
		if (archurTarget[i].y != 987654321) {
			if (mmap[archurTarget[i].y][archurTarget[i].x] == 1) {
				mmap[archurTarget[i].y][archurTarget[i].x] = 0;
				++enemy;
			}
		}
	}
	return enemy;
}

void move() {

	for (int y = N - 1; y >= 1; --y) {
		for (int x = 0; x < M; ++x) {
			mmap[y][x] = mmap[y - 1][x];
		}
	}

	for (int x = 0; x < M; ++x) {
		mmap[0][x] = 0;
	}
}

bool isPlay() {
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			if (mmap[y][x]) return true;
		}
	}
	return false;
}

int simulation() {
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			mmap[y][x] = map[y][x];
		}
	}
	int deleteEnemy = 0;
	while (isPlay()) {

		int oneDeleteEnemy = attack();
		//if (oneDeleteEnemy) cout << oneDeleteEnemy << "\n";
		deleteEnemy += oneDeleteEnemy;
		move();
	}

	return deleteEnemy;
}

void dfs(int cur) {

	if (cur == 3) {
		//시뮬레이션 돌리기.
		ans = max(ans, simulation());
		return;
	}

	for (int x = 0; x < M; ++x) {
		if (!visited[x]) {
			visited[x] = true;
			archur[cur] = { N ,x };
			dfs(cur + 1);
			archur[cur] = { 0,0 };
			visited[x] = false;
		}
	}

	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> D;

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			cin >> map[y][x];
		}
	}

	dfs(0);
	
	cout << ans;
	return 0;
}
}

BOJ 카테고리 내 다른 글 보러가기