BaekJoon 14620번: 꽃길(C++)

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

14620번: 꽃길

풀이법

1) Brute Force로 문제를 해결해 보았다. 실제 들어올 수 있는 배열의 값이 10x10이기에 시간 제한 2초 내에 가능할 것이라 생각하였다.

2) dp 배열을 생성하여, (0,0)부터 (n-1,n-1)까지의 배열 중 값이 들어갈 수 있는 범위인 (1,1)부터 (n-2,n-2) 범위에서 각 index에 들어갈 수 있는 꽃이 있다고 가정 시에, 대지 임대료를 각각 계산해 주었다.

3) 방문한 칸들을 visited배열에 true로 담아주는 visit()함수와 빠져나올 때 vistied배열을 false로 만들어 주는 leave함수를 만들고, for문을 활용하여 경우의 수를 계산해 주었다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

#include <math.h>
#define INF 987654321
using namespace std;

int n;
int arr[11][11];
int dp[11][11];
int vx[5] = {0, 1,0,0,-1 };
int vy[5] = {0, 0,1,-1,0 };
bool visited[11][11];
vector<int> vec;

void visit(int a, int b,int cnt)
{
	for (int i = 0; i < 5; i++)
	{
		int nextX = a + vx[i];
		int nextY = b + vy[i];
		if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= n)
			continue;
		visited[nextX][nextY] = true;
	}

}
void leave(int a, int b,int cnt)
{
	for (int i = 0; i < 5; i++)
	{
		int nextX = a + vx[i];
		int nextY = b + vy[i];
		if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= n)
			continue;
		visited[nextX][nextY]= false;
	}
}
int hap(int a, int b)
{
	int temp=0;
	for (int i = 0; i < 5; i++)
	{
		int nextX = a + vx[i];
		int nextY = b + vy[i];
		temp += arr[nextX][nextY];
	}
	return temp;
}
bool canPush(int a, int b)
{
	for (int i = 0; i < 5; i++)
	{
		int nextX = a + vx[i];
		int nextY = b + vy[i];
		if (visited[nextX][nextY])
			return false;
	}
	return true;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i < n - 1; i++)
	{
		for (int j = 1; j < n - 1; j++)
		{
			dp[i][j]=hap(i, j); //씨앗을 심었을 떄 각 칸의 비용
		}
	}
	for (int i = 1; i < n - 1; i++)
	{
		for (int j = 1; j < n - 1; j++)
		{
			visit(i, j,0);
			for (int k = 1; k < n - 1; k++)
			{
				for (int l = 1; l < n - 1; l++)
				{
					if (canPush(k,l))
					{
						visit(k, l,1);
						for (int o = 1; o < n - 1; o++)
						{
							for (int p = 1; p < n - 1; p++)
							{
								if (canPush(o, p))
								{
									vec.push_back(dp[i][j] + dp[k][l] + dp[o][p]);
								}

							}
						}
						leave(k, l,1);
					}
				}
			}
			leave(i, j,0);
		}
	}
	sort(vec.begin(), vec.end());

	cout << vec[0];
	
}