[백준][완전탐색] 14620 꽃길 c++구현

목차

https://www.acmicpc.net/problem/14620

문제

 

문제 구현 방향

10C3 정도이면 충분히 완전탐색을 할 수 있는 시간이다.

따라서 3개의 꽃을 고른뒤 꽃이 안죽는 것을 체크하고 최솟값을 갱신하는 방식으로 코드를 짰다.

set을 이용하여 꽃이 죽는 중복을 검사 했다.

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
using namespace std;
int n;

int board[11][11] = { 0 };
vector<int>v;
vector<int>comb;
int minSize = 999999;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

//조합 완전 탐색
void combi(int start) {
	if (comb.size() == 3) {
		set<pair<int, int>> s;
        //면적 set에 넣기
		for (int i : comb) {
			int r = i / n;
			int c = i % n;
			s.insert({ r, c });
			for (int i = 0; i < 4; i++) {
				int Nr = r + dy[i];
				int Nc = c + dx[i];
				s.insert({ Nr, Nc });
			}
			
		}
		if (s.size() == 15) {  //중복값 없이 들어가면 총 사이즈가 15가 되어야함
			int num = 0;
			for (auto p = s.begin(); p != s.end(); p++) {
				num += board[(*p).first][(*p).second];

			}
			minSize = min(minSize, num);  //최솟값 갱신
		}
		return;
	}
	for (int i = start; i < v.size(); i++) {
		comb.push_back(v[i]);
		combi(i + 1);
		comb.pop_back();
	}
}

int main() {
	int cnt = 0;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
        //가장자리에서는 어짜피 꽃이 피지 못함
			if (i != 0 && i != n - 1 && j != 0 && j != n - 1) {
				v.push_back(cnt);
			}
			cnt++;
		}
	}
	combi(0);
	cout << minSize;
}