86. 피자배달 거리 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

풀이 

- 앞서 풀었던 조합을 이용해서 피자 가게를 선별한다.

- 모든 가게를 선별하면 ch배열에 선별한 피자가게 번호가 들어간다.

- 이때 레벨은 m과 같아지고 집 <-> 선택한 피자가게(m개) 거리를 구하는데 이 중 가장 작은 값을 dis에 저장 한 후 sum에 더한다.

- 모든 집의 최소 피자배달거리들이 sum에 저장되고 이 때 sum은 도시의 피자배달거리가 된다.

- 한 개 경우(L==m)의 도시의 피자배달거리를 구하면 res와 비교해서 작으면 res를 업데이트 한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, int> > hs;
vector<pair<int, int> > pz;
int ch[20], m, res=2147000000, dis, sum=0;


//86. 피자 배달 거리(DFS)
void DFS(int L, int s){
    if(L==m){
        sum=0;
        for(int i=0;i<hs.size();i++){
            int x1=hs[i].first;
            int y1=hs[i].second;
            dis=2147000000;
            for(int j=0;j<m;j++){
                int x2=pz[ch[j]].first;
                int y2=pz[ch[j]].second;
                dis=min(dis, abs(x1-x2)+abs(y1-y2));
            }
            sum=sum+dis;
        }
        if(sum<res)res=sum;
    }
    else{
        for(int i=s;i<pz.size();i++){
            ch[L]=i;
            DFS(L+1, i+1);
        }
    }
}

int main(){
    int n, a;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>> a;
            if(a==1) hs.push_back(make_pair(i, j)); //집
            else if(a==2) pz.push_back(make_pair(i, j)); //피자가게
        }
    }
    DFS(0, 0);
    cout<<res;
    return 0;
}