[BOJ 21772 // C++] 가희의 고구마 먹방

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 21772번 문제인 가희의 고구마 먹방이다.
문제는 아래 링크를 확인하자.

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

21772번: 가희의 고구마 먹방

상하좌우 움직임 네 가지를 중복을 포함해 10회 나열하는 경우의 수는 4의 10제곱인 1,048,576가지이다. 이 모든 경우의 수는 제한시간 내에 모두 조사하기에 충분히 적다.

 

위의 관찰을 이용해 모든 가능한 상하좌우 움직임을 시도해 문제를 해결하자.

 

가능한 움직임 중 "제자리에 있기"는 특별히 구현하지 않아도 됨을 확인하자. 초기 위치에서 움직일 수 있는 위치가 없는 경우를 제외한다면 항상 T회 움직이는 경우 중에 답이 적어도 하나 존재하기 때문이다.

 

아래는 제출한 소스코드이다.

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

int R, C, T;
int gR, gC;
string board[100];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int func(int r, int c, int moved) {
	if (moved == T) return 0;
	
	int ret = 0; 
	for (int i = 0; i < 4; i++) {
		int rr = r + dr[i], cc = c + dc[i];
		if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == '#') continue;
		if (board[rr][cc] == 'S') {
			board[rr][cc] = '.';
			ret = max(ret, func(rr, cc, moved + 1) + 1);
			board[rr][cc] = 'S';
		}
		else ret = max(ret, func(rr, cc, moved + 1));
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C >> T;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'G') board[r][c] = '.', gR = r, gC = c;
		}
	}

	cout << func(gR, gC, 0);
}