[백준 14620] 꽃길 (C++)

https://www.acmicpc.net/problem/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)이 주어진다.

 

출력

---

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

 

문제 풀이

---

백트래킹 문제.

 

꽃의 중앙을 기점으로 하여 3개의 꽃이 모두 겹쳐지지 않고 심어지는지 확인한다. 심을 수 있다면 해당 위치에 꽃이 심어졌는지 저장하는 boolean 타입 배열에 꽃의 5 위치를 true로 변경한 후, depth를 1증가시킨다. 재귀적으로 호출한 함수를 빠져나왔다면 꽃의 5 위치를 다시 원상복구한다.

1차원 배열이 아니라 2차원 배열에 저장하는 것으로 바뀐 백트래킹 기본 문제.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int** arr;
int N;
bool** isVisited;
int answer;

bool checkPosition(int i, int j)
{
	if (isVisited[i][j] == false && isVisited[i + 1][j] == false && isVisited[i - 1][j] == false && isVisited[i][j + 1] == false && isVisited[i][j - 1] == false)
	{
		return true;
	}
	return false;
}

void set(int i, int j, bool b)
{
	isVisited[i][j] = b;
	isVisited[i + 1][j] = b;
	isVisited[i - 1][j] = b;
	isVisited[i][j - 1] = b;
	isVisited[i][j + 1] = b;
}

void backTracking(int depth, int maxDepth)
{
	if (depth == maxDepth)
	{
		int sum = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (isVisited[i][j] == true)
				{
					sum += arr[i][j];
				}
			}
		}
		answer = min(answer, sum);
	}
	else
	{
		for (int i = 1; i < N-1; i++)
		{
			for (int j = 1; j < N - 1; j++)
			{
				if (checkPosition(i, j) == true)
				{
					set(i, j, true);
					backTracking(depth + 1, maxDepth);
					set(i, j, false);
				}
			}
		}
	}
}

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

	cin >> N;
	arr = new int*[N];
	isVisited = new bool* [N];
	answer = 987654321;
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N];
		isVisited[i] = new bool[N];
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
			isVisited[i][j] = false;
		}
	}
	backTracking(0, 3);
	cout << answer << "\n";
	return 0;
}