[알고리즘] 캐슬 디펜스

포인트

• 조합(궁수의 위치), 움직임, 사냥 을 어떻게 구현을 하는냐가 요점인것 같습니다. 사실 여타 구현 문제에서도 그렇지만 중복된 것을 단일 처리하는 등의 요령이 필요합니다. 그래서 일부 테스트 케이스는 맞지만 다른 것들은 틀릴 수 있는 그런 것들 입니다. 
• 문제를 꼼꼼히, 어떻게 유기적으로 연결하는가가 핵심이네요

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

typedef struct {
    int x;
    int y;
    int Dist;
} enemy;

int n, m, d, answer, temp;
int map[16][16];
int cmap[16][16];
bool visited[16][16];

vector<pair<int, int>> vc;
vector<int> sel;

bool check() {
    bool flag = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (cmap[i][j] == 1) {
                flag = false;
                vc.push_back(make_pair(i, j));
            }
        }
    }
    return flag;
}

bool cmp(enemy A, enemy B) {
    if (A.Dist < B.Dist) return true;
    if (A.Dist == B.Dist) {
        if (A.y < B.y) {
            return true;
        }
    }
    return false;
}

void shot() {
    pair<int, int> target[3];
    for (int i = 0; i < sel.size(); i++) { // 궁수 위치
        int x = n;
        int y = sel[i];
        vector<enemy> targets;

        for (auto ele : vc) { // 적군 좌표에서
            int xx = ele.first;
            int yy = ele.second;

            int dist = abs(x - xx) + abs(y - yy);
            if (dist <= d) {
                enemy enemy;
                enemy.x = xx;
                enemy.y = yy;
                enemy.Dist = dist;
                targets.push_back(enemy);
            }
        }


        if (targets.size() >= 1) { // 1이상이면
            sort(targets.begin(), targets.end(), cmp);
            target[i].first = targets[0].x;
            target[i].second = targets[0].y;
        } else {
            target[i].first = -1;
            target[i].second = -1;
        }
    }

    for (int i = 0; i < 3; i++) {
        int x = target[i].first;
        int y = target[i].second;

        if (x == -1 && y == -1) continue;
        if (!visited[x][y]) {
            visited[x][y] = true;
            cmap[x][y] = 0;
            temp++;
        }
    }
}

void move() {
    for (int i = vc.size() - 1; i >= 0; i--) { // 적으러 부터
        int x = vc[i].first;
        int y = vc[i].second;

        if (cmap[x][y] == 0) continue;
        if (x == n - 1) {
            cmap[x][y] = 0;
        } else {
            cmap[x][y] = 0;
            cmap[x + 1][y] = 1;
        }
    }
}

void kill() {
    memcpy(cmap, map, sizeof(map));
    while (1) {
        vc = {};
        memset(visited, false, sizeof(visited));

        if (check()) break; // 적이 없으면 종료
        shot();
        move();
    }
}

void go(int index, int cnt) { // 조합 만들기
    if (cnt == 3) {
        temp = 0;
        kill();
        answer = max(answer, temp);
        return;
    }

    if (index >= m) return;

    sel.push_back(index);
    go(index + 1, cnt + 1);
    sel.pop_back();

    go(index + 1, cnt);
}

int main() {
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    go(0, 0);
    cout << answer << '\n';
    return 0;
}

python

import sys

sys.stdin = open('input.txt')

from copy import deepcopy


def check(copy: list) -> bool:
	for i in range(n):
		for j in range(m):
			if copy[i][j]:
				return True
	return False


def calc() -> int:
	copy = deepcopy(data)
	kill = 0
	while check(copy):
		total_enemies = set()
		for archer in sel:
			x, y = n, archer
			
			temp_enemies = []
			for i in range(n):
				for j in range(m):
					if copy[i][j] and (abs(x - i) + abs(y - j)) <= d:
						temp_enemies.append([i, j, abs(x - i) + abs(y - j)])
			if temp_enemies:
				temp_enemies.sort(key=lambda x: (x[2], x[1]))
				total_enemies.add((temp_enemies[0][0], temp_enemies[0][1]))
		for row, col in total_enemies:
			copy[row][col] = 0
			kill += 1
		for row in range(n - 1, -1, -1):
			for col in range(m):
				if copy[row][col]:
					if row == n - 1:
						copy[row][col] = 0
					else:
						copy[row][col], copy[row + 1][col] = 0, 1
	return kill


def go(index: int, cnt: int) -> None:
	global answer
	if cnt == 3:
		result = calc()
		answer = max(answer, result)
		return
	
	if index >= m:
		return
	
	sel.append(index)
	go(index + 1, cnt + 1)
	sel.pop()
	
	go(index + 1, cnt)


n, m, d = map(int, input().split())

data = [list(map(int, input().split())) for _ in range(n)]

answer = 0
sel = []

go(0, 0)

print(answer)