[C++,구현,BFS,DFS] 백준 15686번 치킨 배달 문제풀이

문제링크

백준 15686번 치킨 배달

15686번: 치킨 배달

 

DFS,BFS를 모두 쓴 조금은 힘든? 문제이다. 최대 M개의 치킨집을 고르는 건 DFS, 치킨집을 골라 최소거리를 구하는 건 BFS로 구현하였다. 밑에 코드에 나와있듯이 치킨집을 선정할 때 예외처리를 잘 못해줘서 애를 먹었던 문제이다.

#include <iostream>
#include <queue>
using namespace std;
int n,m,ans=1987654321; 
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int map[50][50],dis[50][50],zero[50][50],check[50][50];
vector <pair<int,int> >chickk,chick;
vector <pair<int,int> >house;
 
void copy_map(int (*a)[50],int (*b)[50]){//복사함수
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        a[i][j]=b[i][j];
}
 
void cnt_dis(){
    copy_map(check,zero);//bfs를 위한 방문check 초기화
    queue <pair<int,int> >cchick;
    for(int i=0;i<chickk.size();i++){//벡터에서 큐로 치킨집옮기기
        cchick.push(make_pair(chickk[i].first,chickk[i].second));
        check[chickk[i].first][chickk[i].second]=1;
    }
 
    while(!cchick.empty()){//bfs로 dis배열에 최소거리 계산
        int a=cchick.front().first,b=cchick.front().second;
        
        cchick.pop();
        for(int i=0;i<4;i++){
            int x=a+dx[i],y=b+dy[i];
            if(    x>=0&&x<n&&y>=0&&y<n&&!check[x][y]){
                check[x][y]=1;
                dis[x][y]=dis[a][b]+1;
                cchick.push(make_pair(x,y));
            }
        }
    }
}
 
void dfs(int depth,int x,int y){
    if(depth==m){ //최대 m번 했으면
        copy_map(dis,zero);
        cnt_dis();//거리계산
        int tmp=0;
        for(int i=0;i<house.size();i++){//map에 있는 모든 집거리의 합
            tmp+=dis[house[i].first][house[i].second];
        }
        if(ans>tmp)ans=tmp;//최소값 찾기
        return;
    }
    
    int j=y,flag=0;
    int t_map[50][50];
    for(int i=x;i<n;i++){
        if(flag)j=0;
        for(;j<n;j++){
            flag=1;
            if(map[i][j]==2){
                chickk.push_back(make_pair(i,j));//치킨집 후보들 vector에 넣기
                if(j+1>=n) dfs(depth+1,i+1,0);///j+1될때 예외처리 꼭해주자!!!!
                else dfs(depth+1,i,j+1);//다음 치킨집으로
                chickk.pop_back(); //벡터에서 제외
            }
        }
    }
    
}
main(){
    ios::sync_with_stdio(0);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            cin>>map[i][j];
            if(map[i][j]==1)house.push_back(make_pair(i,j));//집좌표 담기
            else if(map[i][j]==2)chick.push_back(make_pair(i,j));//치킨집 좌표 담기
        }
    for(int i=0;i<chick.size();i++)    dfs(0,chick[i].first,chick[i].second);//치킨집 골라서 dfs
    cout<<ans;
}

입력을 받을 떄 집좌표와 치킨집좌표를 벡터와 저장한 후 

치킨집이 있는 곳을 기준으로 DFS탐색을 하는 dfs함수로 들어간다. 

dfs가 재귀적으로 호출되어 m번 반복됬으면 cnt_dis함수로 거리를 계산한다. 

여기서 거리는 BFS으로 계산하며 치킨집을 기준으로 거리를 계산 한 후 

집의 좌표값을 넣어 합을 구하고 최소값을 도출하는 방식이다.