[백준OJ] 14620번 꽃길

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

14620번: 꽃길

---

 

풀이

N의 값이 매우 작으므로, 완전탐색을 이용해서, 겹치지 않게 서로다른 위치에 3개를 놓을때마다 최솟값을 갱신하는 방법으로 값을 구했다.

 

보통의 완전탐색과 같은데, 이제 꽃을 심으면 동,서,남,북,중앙 5군데를 차지하므로, 이것을 고려해서 문제를 해결해주면 된다.

 

 

코드

#include<iostream>
#include<algorithm>
using namespace std;

int maze[10][10];
bool flower[10][10] = { 0 };
int mv[5][2] = { {0,0},{1,0},{-1,0},{0,1},{0,-1} };
int n,ret=987654321;

//범위안에 있는지 확인하는 함수
bool isIn(int x, int y) {
	return x >= 0 && x < n && y >=0 && y < n;
}

//범위안에 꽃이 있는지 확인하는 함수
bool flower_check(int x, int y) {
	for (int k = 0; k < 5; k++) {
		int nx = x + mv[k][0];
		int ny = y + mv[k][1];
		if (!isIn(nx, ny) || flower[nx][ny]) {
			return false;
		}
	}
	return true;
}

//꽃을 피우고, 피운꽃들의 땅값을 리턴
int blossom(int x, int y) {
	int s = 0;
	for (int k = 0; k < 5; k++) {
		int nx = x + mv[k][0];
		int ny = y + mv[k][1];
		flower[nx][ny] = true;
		s += maze[nx][ny];
	}
	return s;
}

//피웠던 꽃 회수
void falling(int x, int y) {
	for (int k = 0; k < 5; k++) {
		int nx = x + mv[k][0];
		int ny = y + mv[k][1];
		flower[nx][ny] = false;
	}
}

//완전탐색함수
void dfs(int x, int y,int sum,int cnt) {
	if (cnt == 3) {
		ret = min(ret, sum);
		return;
	}
	for (int i = x; i < n - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			if (flower_check(i,j)) {
				int s = blossom(i, j);
				dfs(i, j, sum + s, cnt + 1);
				falling(i, j);
			}
		}
	}
}

void input() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maze[i][j];
		}
	}
}

void solve() {
	input();
	dfs(0, 0, 0, 0);
	cout << ret;
}

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

	solve();
	return 0;
}