[백준/BOJ] 백준 21772번 : 가희의 고구마 먹방

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

21772번: 가희의 고구마 먹방

백트래킹을 이용해, 이동 가능한 시간 동안 이동한 모든 경우의 수를 확인하여 문제를 해결했다.

 

코드

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

int r, c, t;
vector<string> board;
pair<int, int> start;
int dxdy[5][2] = { {0,0},{0,-1},{-1,0},{0,1},{1,0} };

int Solve(pair<int, int> here, int here_time, int eat)
{
	//t초의 시간이 흘렀을때
	if (here_time == t)
		return eat;

	int ret = 0;

	for (int dir = 0; dir < 5; dir++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

		//there이 움직일 수 있는곳일때
		if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board[there.first][there.second] != '#')
		{
			bool can_eat = false;

			//there위치에 고구마가 있을때
			if (board[there.first][there.second] == 'S')
			{
				can_eat = true;
				board[there.first][there.second] = '.'; //해당 고구마를 먹는다
			}

			if (can_eat == false)
				ret = max(ret, Solve(there, here_time + 1, eat));

			else
				ret = max(ret, Solve(there, here_time + 1, eat + 1));

			//원상복구
			if (can_eat == true)
				board[there.first][there.second] = 'S';
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c >> t;

	for (int i = 0; i < r; i++)
	{
		string input;
		cin >> input;

		for (int j = 0; j < c; j++)
		{
			if (input[j] == 'G')
			{
				start = make_pair(i, j);
				input[j] = '.';
			}
		}

		board.push_back(input);
	}

	cout << Solve(start, 0, 0) << "\n";

	return 0;
}