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

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

---

문제)

진우는 민트초코우유를 좋아하는 민초단이다. 힘든 일이 있더라도 민트초코우유 하나를 마시면 기운이 펄펄 솟는다고 한다!

민트초코우유를 너무 좋아하는 나머지 진우는 매일 아침 특정 지역들에서 민트초코우유가 배달된다는 N × N 크기의 2차원 민초마을로 이사를 하였다.

진우는 아침에 눈을 뜨면 집에서 민초마을의 지도를 들고 민트초코우유를 찾으러 출발한다. 이때의 초기 체력은 M이다. 여기에서 체력은 진우가 이동할 수 있는 거리를 나타낸다. 진우는 지도상에서 상, 하, 좌, 우로 1칸씩 이동할 수 있으며 이동하면 체력이 1만큼 줄어든다. 진우가 마을을 돌아다니다가 민트초코우유를 마신다면 체력이 H 만큼 증가하며 진우의 체력이 초기체력 이상으로 올라갈 수 있다. 체력이 0이 되는 순간 진우는 이동할 수 없다.

민트초코를 찾으러 돌아다니다가 마을 한복판에서 체력이 0이 되어 집으로 못 돌아가는 상황은 만들어져서는 안된다. 진우가 얼마나 많은 민트초코우유를 마시고 집으로 돌아올 수 있는지 알아보자.

 

 

 

입력 :

첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다.

두번째 줄부터 N+1번째 줄에 N칸에 걸쳐서 민초마을의 지도가 주어진다. 각 칸은 공백을 두고 주어지며 지도상에서 진우의 집은 1, 민트초코우유는 2로 주어지며 빈 땅은 0으로 주어진다. 진우의 집은 무조건 한 곳이 주어지며 마을에 배달되는 민트초코우유의 총합은 10개를 넘지 않는다.

 

 

 

출력 :

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

 

 

 

 

 

 

 

 

 

풀이)

 

// 20208. 진우의 민트초코우유
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m, h;
 
// 집의 위치
int sx, sy;
 
// 정답을 담을 변수
int ans;
 
// 민초우유의 좌표
vector<pair<int, int>> point;
// 해당 민초를 방문했는지 체크
vector<int> visited;
 
void recur(int x, int y, int health, int cnt)
{
    // 항상 현재 위치에서 집으로 갈 수 있는 지 파악하고
    // 민트초코우유의 최대 개수를 갱신한다.
    int go_home = abs(x - sx) + abs(y - sy);
    if (health >= go_home)
    {
        ans = max(ans, cnt);
    }
 
    for (int i = 0; i < point.size(); i++)
    {
        // i번째 지점까지 가는데 필요한 hp량
        int need_hp = abs(x - point[i].first) + abs(y - point[i].second);
        
        // 방문한 지점이면 continue
        if (visited[i]) continue;
        // 현재 위치에서 해당 위치까지 갈 수 없는 경우
        if (health < need_hp) continue;
        
        visited[i] = 1;
        recur(point[i].first, point[i].second, health - need_hp + h, cnt + 1);
        visited[i] = 0;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> h;
 
    int a;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a;
            // 집의 위치 설정
            if (a == 1)
            {
                sx = i, sy = j;
            }
            // 민초우유의 좌표 파악
            else if (a == 2)
            {
                point.push_back(make_pair(i, j));
            }
        }
    }
 
    // 민초우유의 개수에 맞추어 방문체크 배열 생성
    visited.resize(point.size(), 0);
 
    recur(sx, sy, m, 0);
 
    cout << ans;
 
    return 0;
}

---

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

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