[BOJ]백준 21772번: 가희의 고구마 먹방(C++)/BackTracking

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

21772번: 가희의 고구마 먹방

출처: https://www.acmicpc.net/problem/21772

문제 특성 상 보자마자 어?BFS 할 수 있지만 BFS도 DFS도 아닌 백트래킹 문제 ~~~

왜냐면 이미 지났던 좌표를 다시 가야할 수도 있기 때문이다

그래서 인접한 좌표를 방문할 수 있는 재귀함수를 만들어준 뒤 최대 고구마를 얻을 수 있는 선택 + 현재 좌표에서 얻을 수 있는 고구마를 반환해주엇다

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

typedef struct { int r, c; }point;

int r, c, t, dr[] = { 0,-1,0,1 }, dc[] = { 1,0,-1,0 };
string map[101];
bool visit[101][101];

bool safe(int y, int x) {
	return y >= 0 && y < r && x >= 0 && x < c;
}

int func(point cur, int dep) {
	if (dep > t)return 0;
	int sum = 0;
	if (map[cur.r][cur.c] == 'S') {
		sum = 1;
		map[cur.r][cur.c] = '.';
	}

	int k = 0;
	for (int i = 0; i < 4; i++) {
		int nr = cur.r + dr[i];
		int nc = cur.c + dc[i];

		if (!safe(nr, nc) || map[nr][nc] == '#')continue;
		int f = func({ nr,nc }, dep + 1);
		k = max(k, f);
	}

	if (sum != 0) {
		map[cur.r][cur.c] = 'S';
	}
	return sum + k;
}

int main() {
	cin >> r >> c >> t;
	point cur = { 0,0 };

	for (int i = 0; i < r; i++) {
		cin >> map[i];
		for (int j = 0; j < c; j++)
			if (map[i][j] == 'G')cur = { i,j };
	}
	cout << func(cur, 0);

	return 0;
}

🥔🍠