[17135번] 캐슬 디펜스

17135번: 캐슬 디펜스

 

www.acmicpc.net

삼성 SW역량테스트 A형 기출문제다. 시험 당시는 풀지 못했다.

탐색보단 구현 능력을 중요시 하는 문제같다.

입력을 보고 맵을 이용해서 풀이를 진행하는 경우가 많을 것이다. 나도 그렇게 풀었다.

의도한 방법은 적들의 위치를 리스트에 저장후 거리 별로 정렬 후 진행하는 것 같다.

 

나의 풀이 설계는 맵을 이용해서 시뮬레이션을 하듯 풀었다.

1. 각 궁수 위치를 조합을 통해 지정

2. 각 궁수 위치에서 왼쪽부터 가장 가까운 적을 체크

3. 모든 궁수의 적 체크가 끝났으면 적 카운트를 줄인다.

4. 궁수의 위치(행 인덱스)를 감소

 

적들을 하단으로 전진 시키는 것이 아니라, 궁수의 인덱스만 감소시키면서 맵은 따로 업데이트를 하지 않고 진행하였다.

 

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int N, M, D, ans, map1[17][17], map2[17][17];
vector<int>ArcLoc;
bool chk(int r, int c) {
	if (!(r<1 || c<1 || r>N || c>M))
		return true;
	return false;
}
void GameGo() {
	int tmp = 0, m1[17][17], m2[17][17];
	memcpy(m1, map1, sizeof(m1)); memcpy(m2, map2, sizeof(m2));
	for (int ArcR = N + 1; ArcR > 1; ArcR--) {
		for (int idx = 0; idx < 3; idx++) {
			int ArcC = ArcLoc[idx];
			for (int nowDist = 1; nowDist <= D; nowDist++) {
				bool kill = false;
				for (int d = 1; d <= nowDist; d++) {
					int nr = ArcR - d, nc = ArcC - (nowDist - d);
					if (chk(nr, nc) && m1[nr][nc] == 1) {
						m2[nr][nc]++;
						kill = true;
						break;
					}
				}
				if (kill == true) break;
				for (int d = nowDist - 1; d > 0; d--) {
					int nr = ArcR - d, nc = ArcC + (nowDist - d);
					if (chk(nr, nc) && m1[nr][nc] == 1) {
						m2[nr][nc]++;
						kill = true;
						break;
					}
				}
				if (kill == true) break;
			}
		}
		int Ecnt = 0;
		for (int r = ArcR - 1; r > 0; r--) {
			for (int c = 1; c <= M; c++) {
				if (m1[r][c] == 1)
					Ecnt++;
				if (m2[r][c] != 0) {
					tmp++;
					m1[r][c] = m2[r][c] = 0;
				}
			}
		}
		if (Ecnt == 0) break;
	}
	ans = ans < tmp ? tmp : ans;
}
void setArc(int Acnt, int idx) {
	if (Acnt == 3)
		GameGo();
	else {
		for (int i = idx; i <= M; i++) {
			ArcLoc.push_back(i);
			setArc(Acnt + 1, i + 1);
			ArcLoc.pop_back();
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M >> D;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			cin >> map1[r][c];
	setArc(0, 1);
	cout << ans;
	return 0;
}