백준 14620 C++

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

14620번: 꽃길

n이 결국 10x10이 최대라서 완전탐색하면 쉽게 풀 수 있는데

그저 DP를 할지 진짜 완전탐색을 할지 고민하다가 그냥 완전탐색으로 풀었다.

 

#include <iostream>
#include <vector>

using namespace std;

int n;		// 6<= n <= 10;
int g[15][15];
int visited[15][15];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<int> price;
int minR = 987654321;

bool check(int y, int x)				//씨앗이 심어지는 위치를 y, x라고 하고 꽃잎의 범위가 통과하면 visited와 price를 넣는다.
{
	int temp = -1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (g[ny][nx] == -1 || visited[ny][nx]) break;		//범위를 벗어나거나 이미 꽃이 있는 지역이라면 for문을 나간다.
		
		temp = i;
	}

	if (temp == 3) {		//for문을 끝까지 돌았다면
		int a = 0;
		visited[y][x] = 1;
		a += g[y][x];
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			visited[ny][nx] = 1;		//꽃잎의 부분도 방문처리함.
			a += g[ny][nx];
		}

		price.push_back(a);

		return true;
	}
	else {
		return false;
	}
}

void release(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] = 0;
	}

	price.pop_back();
}

void go(int sy, int sx)
{
	if (price.size() == 3) {
		int a = 0;
		for (auto i : price) {
			a += i;
		}

		minR = min(minR, a);

		return;
	}

	for (int i = sy; i <= n; i++) {
		for (int j = sx; j <= n; j++) {
			//꽃을 심을 수 없는 자리에선 굳이 재귀를 돌릴 필요가 없다. 
			//왜냐면 결국에 go(i)에서도 심을 수 있는 위치를 확인할건데 심은것만 돌리는게 횟수가 작지 다 돌리면 너무 크다고 생각했다.
			//못심으면 그냥 다음 칸을 향해서 나아가는 것이다. 심어지면 심고 go(i)를 통해 다음 칸을 찾아 가는 것이다.

			if (check(i, j)) {		
				go(i, j);
				release(i, j);
			}
		}
		sx = 1;
	}
}


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

	cin >> n;

	fill(&g[0][0], &g[0][0] + 15 * 15, -1);

	for (int i = 1; i <= n; i++) {		//가든 가격 입력
		for (int j = 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}


	go(1, 1);

	cout << minR;

}