[백준] 20208-진우의 민트초코우유(C++)

문제링크: www.acmicpc.net/problem/20208

20208번: 진우의 민트초코우유

 

n*n은 100이므로 각각의 좌표를 전부 검사해주는 행동은 당연히 시간초과

 

"민트초코우유의 총합은 10개를 넘지 않는다." 라는 조건을 사용하여야 합니다. 즉, 각 좌표들의 거리로 탐색해야 합니다.

 

이때, 조합이 아니라 순열구조이므로 10! 만큼 소모될수 있습니다. 시간적으로 괜찮을 것을 확인했다면 

 

바로 구현하면 됩니다.

 

 

정답코드입니다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef struct MyStruct
{
	int y;
	int x;
	bool checked;
}val;

int n = 0, m = 0, h = 0;
int result = 0;
int arr[10][10] = { 0, };
val house;
vector <val> mint;

void dfs(int y, int x,int cur, int cnt, int hp) {
	if (cnt > result) {// 방문횟수가 더 많고
		if (abs(y - house.y) + abs(x - house.x) <= hp)
			result = cnt;
	}
	if (hp <= 0)
		return;
	for (int i = 0; i < mint.size(); i++) {
		
			int len = abs(mint[i].y - y) + abs(mint[i].x - x);
			if (len <= hp && mint[i].checked == 0) {
				mint[i].checked = 1;
				dfs(mint[i].y, mint[i].x, i+1, cnt + 1, hp - len + h);
				mint[i].checked = 0;
			}
			
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> h;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++){
			int temp = 0;
			cin >> temp;
			if (temp == 1)
				house.y = i, house.x = j;
			else if (temp == 2)
				mint.push_back({ i,j,0 });
		}
	}
	
	dfs(house.y,house.x,0, 0, m);
	cout << result  << endl;
	return 0;
}

 

간혹 조합과 수열 구현을 헷갈려 하시는데, 아래 링크 참고하시면 좋을 것 같습니다. 

paris-in-the-rain.tistory.com/35

순열, 조합 알고리즘 - DFS로 구하기(백트래킹), C++, Python