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

최초 업로드: 2025-08-08 23:54:47

최근 수정 시간: 2025-08-08 23:55:40

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] 진우의 민트초코우유

[문제 링크](https://www.acmicpc.net/problem/20208)

## 문제 설명

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

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

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

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

## 입력

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

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

## 출력

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

## 풀이
#### 민트초코우유가 있는 위치가 최대 10곳이기에 백트래킹을 하면 최대 10!의 연산으로 시간 안에 통과가 가능하다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

int n, m, h, maxCnt;
int arr[10][10];
bool visited[10];
vector<pi> milk;
pi start;

int dist(int x1, int y1, int x2, int y2) {
    return abs(x1-x2) + abs(y1-y2);
}

void back(int depth, int hp, int x, int y) {
 if(dist(x, y, start.first, start.second)<=hp) {
 maxCnt = max(maxCnt, depth);
 }
 for(int i=0;i<milk.size();i++) {
 int cost = dist(x, y, milk[i].first, milk[i].second);
 if(!visited[i] && hp>=cost) {
 visited[i]=true;
 back(depth+1, hp-cost+h, milk[i].first, milk[i].second);
 visited[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++) {
 cin >> arr[i][j];
 if(arr[i][j]==2) milk.push_back({i, j});
 else if(arr[i][j]==1) start = {i, j};
 }
 }
 back(0, m, start.first, start.second);
 cout << maxCnt;
}
```