[BOJ/20208] 진우의 민트초코 우유, c++

🔗 링크

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

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

🤯 한줄 후기

스타벅스 민트초코 프라푸치노 개맛있음!

🤷 문제

👩‍💻 풀이

진우의 체력과 현재 마신 민트초코의 개수를 매개변수로 가지고 재귀를 돌면된다.

이때 재밌는 것은 집에서 부터 상하좌우로 이동할 필요 없이 민트 초코 위치만 저장해두고 수식으로 거리를 구할 수 있다.

집 (x, y) 와 민트초코 (a, b) 의 거리 distance = | x - a | + | y - b | 이다. 따라서 민트 초코 위치랑 집의 위치만 저장해놓고 거리를 구하면서 체력을 계산해준다. 다음 민트 초코 위치에서의 체력은 ( 현재 체력 + H - 거리 ) 이다.

백트래킹 문제로 종료 조건은 체력이 0보다 작거나 같아진 경우, 모든 민트 초코를 방문한 경우이다.

재귀를 돌 때마다 민트초코 개수가 현재 최댓값보다 커진다면 변경해준다.

💻 코드

//AC
//BOJ 20208 진우의 민트초코 우유
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int  N, H, ans, homex, homey;
struct Mint {
    int x;
    int y;
    int check;
};
vector<Mint> v;
void solve(int x, int y, int M, int cnt) {
    if (cnt > ans) {
        if(abs(x - homex) + abs(y - homey) <= M)    ans = cnt;
        
    }
    if (M <= 0 || cnt == v.size()) return;
    for (Mint& mint : v) {
        int dist = abs(mint.x - x) + abs(mint.y - y);
        if (dist <= M && !mint.check) {
            mint.check = 1;
            solve(mint.x, mint.y, M + H - dist, cnt + 1);
            mint.check = 0;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int M, temp;
    cin >> N >> M >> H;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> temp;
            if(temp == 1) {
                homex = i;  homey = j;
            }
            else if(temp == 2) {
                v.push_back({i, j, 0});
            }
        }
    }
    solve(homex, homey, M, 0);
    cout << ans;
    return 0;
}