[백준/BOJ] 14620번 꽃길

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

14620번: 꽃길

쉬운 DFS 문제였다. 씨앗을 3개 심을 수 있는 모든 경우의 수를 구한 후, 해당 케이스가 꽃이 피어날 수 있는지를 확인하면 된다. 배열을 여러 개 두면 쉽게 구현할 수 있다. (코드 참고)

 

#include<bits/stdc++.h>
#define f first
#define s second
#define lp1(i, x, n) for(int i = x; i <= n; i++)
using namespace std;
typedef long long ll;

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

int t, n, m, h, k, sx, sy, ex, ey, x, y, z, answer = 2147000000, L, R, _x1, _x2, _y1, _y2, flag, sum;
int board[11][11], visited[11][11], bloomed[11][11]; // 가격, 씨앗, 꽃잎의 위치를 저장할 배열
vector<pair<int, int>> v; // 씨앗을 3개 심은 위치를 저장

// 꽃이 펼 수 있는지 확인
bool check() {
	int tmp_sum = 0;
	memset(bloomed, 0, sizeof(bloomed));
	for(int i = 0; i < v.size(); i++) {
		int x = v[i].f;
		int y = v[i].s;
 		tmp_sum += board[x][y];
		for(int j = 0; j < 4; j++) {
			int nx = x + dx[j];
			int ny = y + dy[j];
			if(visited[nx][ny] || bloomed[nx][ny]) return false;
			bloomed[nx][ny] = 1;
			tmp_sum += board[nx][ny]; 
		}
		if(tmp_sum >= answer) return false;
	}
	
	sum = tmp_sum;
	return true;
}

// 씨앗을 3개 심는 경우의 수 구하기
void DFS(int cnt) {
	if(cnt == 3) {
		if(check()) answer = min(answer, sum);
		return;
	}
	
    // 범위를 벗어나지 않는 곳에서 시작/끝 지점을 잡았다.
	for(int i = 1; i < n - 1; i++) {
		for(int j = 1; j < n - 1; j++) {
			if(visited[i][j] == 0) {
				visited[i][j] = 1;
				v.push_back({ i, j });
				DFS(cnt + 1);
				visited[i][j] = 0;
				v.pop_back();
			}	
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	
	DFS(0);
	cout << answer;
}