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

문제 링크 : www.acmicpc.net/problem/20208

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

이 문제에서 주의해야할 점이 있다. 

(1) 우유를 많이 먹고 끝내는게 아니라, 우유를 많이 먹고 집으로 되돌아와야 한다.

(2) 출발지와 목적지가 정해져있다.

 

문제를 대충 읽은 탓에 집으로 되돌아오는 조건을 빼먹었고, 결국 두어차례 오답을 겪게되었다.

또한 (2)번 역시 매우 중요한 포인트인데, 출발지점과 목적지점이 뚜렷하며 동시에 중도 포기 조건 (return) 또한 명시되어있기에, 내가 지나간 지점들을 일일이 bool문으로 확인하지 않아도 된다. 

 

무슨 말이냐 하면, 아래 코드에서 왔다갔다한 지점들을 bool문으로 기억 + memset으로 초기화 하는 코드를 읽어보면 된다.

(1) 실패 케이스

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

int maxi = 0, n = 0, m = 0, h = 0, my[4] = {0,1,0,-1}, mx[4] = {1,0,-1,0}, arr[11][11];
pair<int,int> start;
vector<pair<int,int>> mint;
bool ch[11][11] = {false,}, ate[11] = {false,};

void dfs(int y, int x, int dy, int dx, int health, int cnt){
    ch[y][x] = true;
    if(y==dy&&x==dx&&health>=0){
        if(abs(y+x-start.first-start.second)>health+h) return;
        if(maxi<cnt+1) maxi = cnt+1;
        for(int i=0; i<mint.size(); i++){
            if(!ate[i]){
                ate[i] = true;
                memset(ch,0,sizeof(ch));
                dfs(y,x,mint[i].first,mint[i].second, health+h, cnt+1);
                ate[i] = false;
            }
        }
    }
    if(health<0||maxi>=mint.size()) return;
    for(int i=0; i<4; i++){
        int ny = y+my[i];
        int nx = x+mx[i];
        if(ny>=1&&ny<=n&&nx>=1&&nx<=n&&!ch[ny][nx]) dfs(ny,nx,dy,dx,health-1,cnt);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> h;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> arr[i][j];
            if(arr[i][j]==1) start.first=i,start.second=j;
            else if(arr[i][j]==2) mint.push_back(make_pair(i,j));
        }
    }
    for(int i=0; i<mint.size(); i++){
        if(!ate[i]){
            ate[i] = true;
            dfs(start.first, start.second, mint[i].first, mint[i].second, m, 0);
            ate[i] = false;
            memset(ch,0,sizeof(ch));
        }
    }
    cout << maxi << "\n";
   return 0;
}

이 코드는 테스트 케이스는 통과했으나, 3%쯤 채점할 무렵 실패를 겪고 말았다. 

테스트케이스가 충분하지 않아서 정확히 어떤 케이스에서 실패한 것인지는 모르지만, 문득 코드를 곰곰히보니

(1) 출발지점이 명확함 (2) 도착지점도 명확함 (3) 중간에 return이 되는 중단 포인트들도 명확함

이 3가지를 결합하여 일일이 지나온 지점들을 check하지 않아도 된다는 것을 깨달았다. 

 

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

struct mint{
    int y;
    int x;
    int checked;
};

int n=0,m=0,h=0,ans=0, arr[11][11];
vector<mint> v;
pair<int,int> start;

void dfs(int y, int x, int cnt, int health){
    if(cnt>ans){
        if(abs(y-start.first)+abs(x-start.second)<=health) ans = cnt;
    }
    if(health<=0||cnt==v.size()) return;
    for(int i=0; i<v.size(); i++){
        int newdis = abs(y-v[i].y)+abs(x-v[i].x);
        if(v[i].checked==0&&newdis<=health){
            v[i].checked=1;
            dfs(v[i].y,v[i].x,cnt+1,health-newdis+h);
            v[i].checked=0;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> h;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> arr[i][j];
            if(arr[i][j]==1) start.first = i, start.second = j;
            else if(arr[i][j]==2) v.push_back({i,j,0});
        }
    }
    dfs(start.first, start.second, 0, m);
    cout << ans << "\n";
   return 0;
}

정답 코드에서는 간단하게 출발지점 / 먹은 민트초코 갯수 / 남은 체력만을 활용해서 dfs를 구현했다. 

앞에서 몇 차례 언급했듯이 출발지점과 도착지점이 명확하기 때문에 굳이 dfs함수의 인자들을 늘려서 왔던 지점들을 체크할 필요가 없다.