[백준/c++] 14620 꽃길

문제

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력

꽃을 심기 위한 최소 비용을 출력한다.

구현해야 할 조건

꽃을 중심에 넣고 빼고 넣고 빼고 계속해서 진행하면 됩니다. 그 중 가장 적은 값을 구하는 위치에 꽃을 놓으면 됩니다.

code

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

#define MAX 11
using namespace std;

const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};

int n;
int res = 987654321;
int board[MAX][MAX];
bool visited[MAX][MAX];

vector<pair<int,int> > v;

bool chk(int y, int x){
	
	if(visited[y][x]) return false;
	
	for(int i = 0; i < 4; i++){
		
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(!(0 <= ny && ny < n && 0 <= nx && nx < n) || visited[ny][nx])
			return false;
	}
	
	return true;
}

int setFlower(int y, int x){
	
	visited[y][x] = true;
	int sum = board[y][x];
	
	for(int i = 0; i < 4; i++){
		
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		visited[ny][nx] = true;
		sum += board[ny][nx];
		
	}
	
	return sum;
}

void eraseFlower(int y, int x){
	
	visited[y][x] = 0;

	for(int i = 0; i < 4; i++){
		
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		visited[ny][nx] = false;
		
	}
	
}

void DFS(int cnt, int sum)
{
	if(cnt == 3){
		
		res = min(res,sum);
		return;
		
	}
	
	for(int i = 0; i < n; i++){
		
		for(int j = 0; j < n; j++){
			
			if(chk(i,j)){
				
				DFS(cnt+1, sum + setFlower(i,j));
				eraseFlower(i,j);
			}
			
		}
		
	}
	
	
}

int main()
{
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> board[i][j];
		}
	}
	
	DFS(0,0);
	
	cout << res;
	
	return 0;
}