[G5] 백준 21772번 가희의 고구마 먹방 C++ 백트래킹

리뷰

 

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

최대 t초간 맵을 순회하며 고구마를 가장 많이 먹을 수 있는 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• a : 맵 정보를 저장할 2차원 배열
• n, m : 맵의 세로/가로 크기를 저장할 변수
• t : 순회할 수 있는 최대 시간을 저장할 변수
• ans : 먹은 고구마의 최대 개수를 저장할 변수
• dx, dy : 5방향 탐색을 위한 방향 배열

 

함수

1. bt

void bt(int cx, int cy, int ct, int ce) {
	if (ct == t) {
		ans = max(ans, ce);
		return;
	}

	for (int i = 0; i < 5; ++i) {
		int nx = cx + dx[i], ny = cy + dy[i];

		if (0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] != -1) {
			if (a[nx][ny]) {
				a[nx][ny] = 0;
				bt(nx, ny, ct + 1, ce + 1);
				a[nx][ny] = 1;
			}
			else bt(nx, ny, ct + 1, ce);
		}
	}
}

 

맵을 탐색하며 고구마를 먹을 수 있는 모든 경우의 수를 탐색하고, 먹은 고구마의 최대 개수를 찾기 위한 함수

 

 

문제풀이

1. n, m, t값을 입력 받고, 변수 sx, sy를 -1로 초기화한다.
2. n*m크기의 맵 정보를 입력 받아 a배열에 장애물일 경우 -1, 고구마일 경우 1, 초기 위치일 경우 sx, sy를 초기화한다.
3. bt함수에 sx, sy, 0, 0을 매개변수로 전달하여 호출한다.
4. bt함수 내부에서 변수 cx, cy, ct, ce에 매개변수를 파싱한다.
5. 기저 조건으로 ct가 t에 도달한 경우 ans와 ce중 더 큰 값을 ans에 저장하고 리턴한다.
6. 4방향을 순회하며 맵의 범위 내이면서 장애물이 아닐 경우 이동을 진행한다.
7. 이동한 위치에 고구마가 있을 경우 고구마를 먹고 재귀를 수행한 뒤 재귀를 빠져나오며 고구마를 다시 놓는다.
8. 이동한 위치에 고구마가 없을 경우 재귀를 수행한다.
9. bt함수가 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 맵의 범위가 최대 100*100으로 작은 편은 아니지만 T값이 최대 10이므로 백트래킹을 수행해도 시간이 넉넉하다.
2. 이동하지 않고 그 자리에 머무르는 것은 의미가 있을까 싶긴 한데 우선은 구현을 해주었다.
3. 고구마를 먹고 다시 돌아가는 경우가 있어야 하므로 별도의 방문 처리를 해주지않았다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 100;
int a[N][N];
int n, m, t, ans;
int dx[] = { 1, -1, 0, 0, 0 };
int dy[] = { 0, 0, 1, -1, 0 };

void bt(int cx, int cy, int ct, int ce) {
	if (ct == t) {
		ans = max(ans, ce);
		return;
	}

	for (int i = 0; i < 5; ++i) {
		int nx = cx + dx[i], ny = cy + dy[i];

		if (0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] != -1) {
			if (a[nx][ny]) {
				a[nx][ny] = 0;
				bt(nx, ny, ct + 1, ce + 1);
				a[nx][ny] = 1;
			}
			else bt(nx, ny, ct + 1, ce);
		}
	}
}

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

	cin >> n >> m >> t;
	int sx = -1, sy = -1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char c; cin >> c;
			if (c == '#') a[i][j] = -1;
			else if (c == 'S') a[i][j] = 1;
			else if (c == 'G') sx = i, sy = j;
		}
	}

	bt(sx, sy, 0, 0);
	cout << ans;
}