문제

문제 링크

해설

• 단순 구현 문제입니다.
• 화단은 최대 10×10이고 씨앗은 총 3개이므로 충분히 bruteforce로 검사할 수 있습니다.
• 꽃은 4방향으로 피기 때문에 좌표는 (1, 1)부터 (N - 2, N - 2)까지만 검사하면 범위를 넘어가서 죽는 꽃을 굳이 검사하지 않아도 되고 검사 횟수를 줄일 수 있습니다.
• 2차원 배열의 인덱스는 정수 하나로 표현할 수 있습니다. i / N은 행의 좌표, i % N은 열의 좌표입니다.
• 씨앗의 개수가 3개이므로 3중 for 루프를 사용해서 모든 씨앗이 꽃을 피울 수 있는지 여부를 검사한 화단 대여값의 최솟값을 검사합니다.

코드

#include <iostream>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int N, answer = 1e9, ground[10][10];
bool seed[10][10];

bool grow_flower(int idx)
{
	int y = idx / N, x = idx % N;

	pair<int, int> pos[5] = {{y, x}, };

	for (int i = 0; i < 4; i++) {
		int ny = y + d[i][0], nx = x + d[i][1];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N || seed[ny][nx]) return false;
		pos[i + 1] = {ny, nx};
	}
	for (auto p : pos) seed[p.first][p.second] = true;
	return true;
}

void destroy_flower(int idx)
{
	int y = idx / N, x = idx % N;
	seed[y][x] = false;
	for (auto i : d) seed[y + i[0]][x + i[1]] = false;
}

int get_cost(int idx)
{
	int cost = 0;
	int y = idx / N, x = idx % N;
	
	cost += ground[y][x];
	for (auto i : d) cost += ground[y + i[0]][x + i[1]];
	
	return cost;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			cin >> ground[y][x];

	int max_idx = N * (N - 1);
	for (int i = N + 1; i < max_idx; i++) {
		if (!grow_flower(i)) continue;
		int cost_flower1 = get_cost(i);
		for (int j = i + 1; j < max_idx; j++) {
			if (!grow_flower(j)) continue;
			int cost_flower2 = get_cost(j);
			for (int k = j + 1; k < max_idx; k++) {
				if (!grow_flower(k)) continue;
				int cost_flower3 = get_cost(k);
			    answer = min(answer, cost_flower1 + cost_flower2 + cost_flower3);
				destroy_flower(k);
			}
			destroy_flower(j);
		}
		destroy_flower(i);
	}
	cout << answer << '\n';
	return 0;
}

소스코드 링크

결과