백준 꽃길 14620

[문제풀이]

 

 2차원 격자판에 씨를 심어서 꽃이 피게한다.

씨앗은 씨앗을 기준으로 상하좌우에 다른 꽃이 존재하지 않을 경우에만 놓을 수 있다.

씨앗을 '3'개 배치 완료 하였을 때 필요한 최소 비용을 구하자.

 

문제 조건:

 

                  (1)  화단의 한 변의 길이 N(6≤N≤10)

                  (2)  N개씩 화단의 지점당 가격(0≤G≤200)

           

알고리즘 분석:

 

                   (1) 백트래킹

                   (2) 완전 탐색

 

백트래킹을 활용한 완전 탐색 문제,  2차원 배열에 조건에 맞으면 씨앗을 심어서 꽃을 피워 보고,

꽃이 3개가 되었으면 결과 중에 최소값을 저장한다.

재귀 함수를 통해 놓을 수 있는 곳에 다 배치해보고 최소값을 출력해주면 되는 간단한 문제.

 

                 

#include<cstdio>
using namespace std;
int N;
int A[10][10];
bool used[10][10];
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
int ans = 987654321;
bool oob(int y, int x)
{
	if (y < 0 || y >= N || x < 0 || x >= N) return false;
	return true;
}
bool can(int y,int x)
{
	if (used[y][x]) return false;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (!oob(ny, nx)) return false;
		if (used[ny][nx]) return false;
	}
	return true;
}

int Fill(int y, int x)
{
	int sum = 0;
	sum += A[y][x];
	used[y][x] ^= 1;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (!oob(ny, nx)) continue;
		used[ny][nx] ^= 1;
		sum += A[ny][nx];
	}
	return sum;
}


void go(int y, int x,int f,int sum)
{
	if (sum > ans) return;
	if (f == 3)
	{
		if (ans > sum) ans = sum;
		return;
	}
	for (int i = y; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (can(i, j))
			{
				int res = Fill(i, j);
				go(i, j, f + 1, sum + res);
				Fill(i, j);
			}
		}
	}
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf("%d", &A[i][j]);
	go(0, 0, 0, 0);
	printf("%d", ans);
}