[BaekJoon] 삼성 sw 역량 테스트(치킨 배달)

• 이 문제는 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

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


int n,m;
int arr[100][100];
int result=987987987;

// dfs를 이용하여 check배열에 치킨집 표시
// 이렇게 2차원 배열보다 1차원 Node 배열을 만드는 것이 시간을 줄이는 길이다.
void dfs(int y,int x,bool check[100][100],int cnt){
    if(cnt==m){
        int total=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(arr[i][j]==1){
                    int sum=987987987;
                    for(int a=0;a<n;a++){
                        for(int b=0;b<n;b++){
                            if(check[a][b]){
                                int temp=abs(i-a)+abs(j-b);
                                sum=min(sum,temp);
                            }
                        }
                    }
                    total+=sum;
                }
            }
        }
        result=min(result,total);
    }
    else{
        for(int i=y;i<n;i++){
            for(int j=0;j<n;j++){
                if(arr[i][j]==2 && !check[i][j]){
                    check[i][j]=1;
                    dfs(i,j,check,cnt+1);
                    check[i][j]=0;
                }
                
            }
        }
    }
}

int main(){
    cin>>n>>m;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
        }
    }
    
    bool check[100][100]={0};
    dfs(0,0,check,0);
    
    cout<<result;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.