백준 20208번 진우의 민트초코우유 (C++)

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

20208번: 진우의 민트초코우유

 

이전에 풀어본 문제들을 다시 풀어보는 프로젝트(?)를 진행중이다. 문제 양치기보다 각 문제들을 더 잘 파악하는게 좋을 것 같다는 생각이 들었다. 모든 문제를 내 힘으로 푼 것도 아니기 때문이다. 

 

1. 문제 조건

- 가능한 많은 초코우유를 마시고 돌아올 수 있는 최대 민트초코우유 개수를 찾아낸다.

 

2. 접근법

- 먼저 보고 생각나는 건 DFS 완전탐색이다. 그리고 이것은 틀린 생각은 아니다. 그러나 시간 복잡도를 고민하지 않을 수 없다. 각 타일은 4방향으로 나아갈 수 있기 때문에 4^N이 되는데 N => 10이므로 총 타일의 수는 100개이므로 4의 100승이다.  이는 터무니없이 높은 숫자이기 때문에 풀어낼 수 없다. 

먼저 여기서 알 수 있는것은 이미 초코우유의 위치를 모두 알 고 있다는 것이다. 그러므로 초코우유로 바로 직행하면서 백트래킹 해야한다는 아이디어를 얻을 수 있다.

 

dfs{

    if ( visited  == false )  다음 초코우유를 먹은적이 없다면

               visited = true

               if(다음 초코우유까지 갈 체력이 된다면)  dfs 

              visited = false   ------------------> 백트래킹

}

 

그리고 중요한 것은 답을 갱신하는 부분이다. 지금부터 다시 집으로 돌아갈 수 있어야 정답이 될 수 있다. 모든 먹은 우유 개수를 답으로 처리해선 안된다.

 

dfs ( 지금까지 먹은 초코우유의 수 )

  if(지금 체력으로 집에 돌아갈 수 있음 )

        answer = max(answer, 지금까지 먹은 초코우유의 수)

 

그리고 이것은 내가 실수한 부분인데, 위의 정답갱신 조건을 

 

  if(다음 초코우유까지 갈 체력이 된다면)  dfs  

 

이 부분에 함께 넣으면 안된다. 다음 우유를 먹고 집으로 돌아갈 수 없더라도 주변의 초코우유를 먹고 체력을 얻어 집으로 돌아갈 수도 있기 때문이다. 

 

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

vector<pair<int, int>> milks;
bool visited[11] = { false };
int hx, hy;
int N, M, H;
int answer = 0;
void backtracking(int nx, int ny, int cnt, int hp) {
	if (abs(nx - hx) + abs(ny - hy) <= hp) // 이것이 필요한 이유: 비록 지금 돌아갈 수 없더라도, 다른곳에서 우유로 충전한 후에 도착이 가능할 수 있다.
		answer = max(answer, cnt);

	for (int i = 0; i < milks.size(); i++) {
		int milkx = milks[i].first;
		int milky = milks[i].second;
		int cost = abs(milkx - nx) + abs(milky - ny);
		int comeback_cost = abs(milkx - hx) + abs(milky - hy);

		if (visited[i] == false) {
			visited[i] = true;
			if (hp - cost >= 0) {
				backtracking(milkx, milky, cnt + 1, hp - cost + H);
			}
			visited[i] = false;
		}
	}
}

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

	cin >> N >> M >> H;

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

	backtracking(hx, hy, 0, M);

	cout << answer << '\n';
}