[G5] 백준 20208번 진우의 민트초코우유 C++ 백트래킹

리뷰

 

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

진우가 집을 나와서 다시 집으로 돌아올 때 까지 마실 수 있는 민트초코우유의 최대 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 지도의 한변의 크기를 저장할 변수
• m : 초기 체력값을 저장할 변수
• h : 우유를 마실 경우 증가하는 체력 수치를 저장할 변수
• ans : 우유를 마신 최대 개수를 저장할 변수
• mx : 우유의 개수를 저장할 변수
• v : 우유에 방문 여부를 저장할 배열
• Pos : 위치 정보를 정의할 구조체
• milks : 우유의 위치 정보를 저장할 Pos타입 벡터
• hx, hy : 집의 위치를 저장할 변수

 

함수

1. get_dist

int get_dist(int cx, int cy, int dx, int dy) {
	return abs(dy - cy) + abs(dx - cx);
}

 

두 좌표 사이의 거리를 구하기 위한 함수

 

2. bt

void bt(int level, int cnt, int ch, int cx, int cy) {
	if (ans - cnt >= mx - level) return;
	int dist = get_dist(cx, cy, hx, hy);
	if (dist <= ch) ans = max(ans, cnt);
	if (level == mx) return;

	for (int i = 0; i < mx; ++i) {
		if (v[i]) continue;

		const Pos& pos = milks[i];
		int nx = pos.x, ny = pos.y;

		int dist = get_dist(cx, cy, nx, ny);
		//cout << cx << " " << cy << " " << nx << " " << ny << " " << dist << "\n";
		if (dist <= ch) {
			v[i] = true;
			bt(level + 1, cnt + 1, ch - dist + h, nx, ny);
			v[i] = false;
		}
	}
}

 

백트래킹을 통해 모든 집과 우유사이를 이동하며 방문이 가능한지를 체크하고 방문한 개수를 저장하기 위한 함수

 

 

문제풀이

1. n, m, h값을 입력받고, n*n크기의 맵 정보를 입력 받아 우유와 집 정보를 저장한다.
2. mx를 milks의 크기로 저장하고, bt함수에 0, 0, m, hx, hy를 매개변수로 전달하여 호출한다.
3. bt함수 내부에선 변수 level, cnt, ch, cx, cy에 각각의 매개변수 값을 전달받는다.
4. 첫 번째 기저 조건으로 ans-cnt가 mx-level이상일 경우 조기 종료한다.
5. 변수 dist에 get_dist함수를 통해 현재 위치와 집의 위치간의 거리를 저장한다.
6. dist가 ch이하인 경우 집에 돌아갈 수 있는 경우이니 ans와 cnt를 비교해 더 큰값을 ans에 저장한다.
7. 두 번째 기저 조건으로 level이 mx에 도달한 경우 리턴처리하여 범위를 벗어나는걸 막아준다.
8. 0~mx-1인덱스를 순회하며 이미 방문한 우유인 경우 continue처리한다.
9. 변수 nx, ny에 방문할 위치를 파싱하고, 변수 dist에 get_dist함수를 통해 현재 위치와 이동 위치간 거리를 저장한다.
10. dist가 ch이하일 경우 이동할 위치를 방문처리하고 재귀를 수행한다. 재귀를 빠져나온 후 방문을 해제한다.
11. 탐색이 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. 첫 코드 제출 시 소요 시간이 168ms가 나와서 맘에 들지 않아 리팩토링을 진행했다.
2. 현재 상태에서 남은 우유를 모두 마실 수 있어도 ans보다 작은 경우를 가지치기하는 로직을 추가했다.
3. if (ans - cnt >= mx - level) return;에서 mx를 m으로 작성해 WA를 받았고, mx로 수정 후 AC를 받았다.

 

참고 사항

1. 마을에 배달되는 민트초코우유의 총합은 10개를 넘지 않는다.
2. 민트초코우유를 마신다면 체력이 H 만큼 증가하며 진우의 체력이 초기체력 이상으로 올라갈 수 있다.
3. 리팩토링 작업 후 시간이 168ms->20ms가 되었다. 0ms도 가능한 걸 보니 추가 가지치기 가능한 부분이 있나보다.

 

정답 코드

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

const int N = 10;
int n, m, h, ans, mx;
bool v[N];
struct Pos {
	int x, y;
};
vector<Pos> milks;
int hx, hy;

int get_dist(int cx, int cy, int dx, int dy) {
	return abs(dy - cy) + abs(dx - cx);
}

void bt(int level, int cnt, int ch, int cx, int cy) {
	if (ans - cnt >= mx - level) return;
	int dist = get_dist(cx, cy, hx, hy);
	if (dist <= ch) ans = max(ans, cnt);
	if (level == mx) return;

	for (int i = 0; i < mx; ++i) {
		if (v[i]) continue;

		const Pos& pos = milks[i];
		int nx = pos.x, ny = pos.y;

		int dist = get_dist(cx, cy, nx, ny);
		//cout << cx << " " << cy << " " << nx << " " << ny << " " << dist << "\n";
		if (dist <= ch) {
			v[i] = true;
			bt(level + 1, cnt + 1, ch - dist + h, nx, ny);
			v[i] = false;
		}
	}
}

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

	cin >> n >> m >> h;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int k; cin >> k;
			if (k == 2) milks.push_back({ i, j });
			else if (k == 1) hx = i, hy = j;
		}
	}

	mx = milks.size();
	bt(0, 0, m, hx, hy);
	cout << ans;
}