백준 14620 꽃길 c++ (조합)

문제 출처 : https://www.acmicpc.net/problem/14620

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)이 주어진다.

출력

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

알고리즘 분류

• 브루트포스 알고리즘

풀이

조합이라 적은 문제는 대부분 완전탐색(브루트포스) 알고리즘에 속한다.

우선 꽃이 피는 자리는 그래프의 테두리에 있는 경우는 없기 때문에,

row : 1~n-1

col : 1~n-1

만 탐색하면 된다.

그래프의 크기는 최대 10*10이기 때문에, graph[1][1]부터 graph[n-1][n-1]까지 하나의 좌표에 꽃을 심고,

나머지 한 좌표를 찾고, 마지막 한 좌표를 찾는 방식의 조합 알고리즘으로 풀면 된다.

한 좌표에 꽃을 심는 것은, 해당 좌표 포함 인접한 4칸의 좌표를 모두 visited =true로 체크해 준다.

따라서 꽃을 심을 수 있는 경우는 현재 꽃을 심을 좌표의 인접한 칸에 꽃이 피어있지 않은 경우만 꽃을 심으면서 탐색해 준다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;
//6<=n<=10
int graph[10][10];
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visited[10][10];
int result = 987654321;

void resetDir(int r, int c) {
	visited[r][c] = false;

	for (int i = 0; i < 4; i++) {
		int nR = r + dir[i][0];
		int nC = c + dir[i][1];
		visited[nR][nC] = false;	
	}
}

int sumDir(int r, int c) {
	//꽃이 죽는 경우는 visited를 건들지 않는다.
	for (int i = 0; i < 4; i++) {
		int nR = r + dir[i][0];
		int nC = c + dir[i][1];
		if (visited[nR][nC]) {
			return -1;
		}	
	}
	//꽃이 죽지 않는 경우 visited true 체크해주고 sum return
	int sum = graph[r][c];
	for (int i = 0; i < 4; i++) {
		int nR = r + dir[i][0];
		int nC = c + dir[i][1];
		visited[nR][nC] = true;
		sum += graph[nR][nC];
	}
	return sum;
}

void dfs(int r,int c, int cnt,int cost) {
	if (cnt == 3) {
		result = min(result, cost);
		return;
	}
	for (int i = r; i < n - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			if (visited[i][j])continue;
			int sum = sumDir(i, j);
			//꽃이 죽지 않으면 다음 꽃 찾기
			if(sum!=-1) {
				dfs(i, j, cnt + 1, cost + sum);
				resetDir(i, j);
			}
		}
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
		}
	}

	
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			int sum= sumDir(i, j);
			dfs(i, j, 1, sum);
			resetDir(i, j);
		}
	}
	cout << result;

	return 0;
}