[삼성SWTest준비] 15686번 치킨 배달

URL : https://www.acmicpc.net/problem/15686

삼성SW 기출 문제 한 번에 보기 : https://www.acmicpc.net/workbook/view/1152

※삼성 SW 역량평가 기출문제 어떻게 풀지?※

- 아직.... 시간초과 때문에 해결이 안됨....

1. 문제 이해

 - 도시 치킨 거리 = 모든 집의 치킨 거리 합

 - 시간 복잡도 O(집의 갯수 * 치킨 집 C(조합) M)

 - 관점으로 집을 기준? or 치킨집을 기준?(나는 치킨집을 기준)

2. 어떻게 품?

 - 재귀함수로 치킨집 개수를 바탕으로 순열 만든다.

 - 치킨집 폐업 수에 다다르면 지도를 갱신하여 도시 치킨 거리를 구하고 최소값을 저장

※필요 역량 정리하기!!!※

1. 브루트 포스

2. 재귀를 통한 순열

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
int n, m;
int map[51][51];
int visit[51][51] = { 0 };
 
int Min = 9999999;
struct info {
    int x;
    int y;
    bool out;
};
vector<info> chicken;
vector<pair<int, int> > home;
 
int distance(int x1, int y1, int x2, int y2) {
    int x, y;
    if (x1 > x2) {
        x = x1 - x2;
    }
    else {
        x = x2 - x1;
    }
    if (y1 > y2) {
        y = y1 - y2;
    }
    else {
        y = y2 - y1;
    }
    return x + y;
}
 
void check() { // 음식점 갯수 체크
    int home_size = home.size();
    int chicken_size = chicken.size();
    
    for (int j = 0; j < chicken_size; j++) {
        if (chicken[j].out == true)
            continue;
        else {
            for (int i = 0; i < home_size; i++) {
                visit[home[i].first][home[i].second] = distance(chicken[j].x, chicken[j].y,home[i].first, home[i].second);
            }
        }
    }
    int ret = 0;
    for (int i = 0; i < home_size; i++) {
        ret += visit[home[i].first][home[i].second];
    }
    Min = min(Min, ret);
}
 
void go(int index) { // 치킨집 폐업에 따라 진행(순열)
    int chicken_size = chicken.size();
    int chicken_out = chicken.size() - m;
    
    if (chicken_out == index) {
        check();
        return;
    }
    for (int i = index+1; i < chicken_size; i++) {
        chicken[i].out = true;
        go(index + 1);
        chicken[i].out = false;
    }
}
 
int main() {
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) {
                chicken.push_back({i,j,false});
            }
            else if (map[i][j] == 1) {
                home.push_back(make_pair(i, j));
            }
            visit[i][j] = 99999999;
        }
    }
    go(0);
    /*
    int home_size = home.size();
    for (int i = 0; i < home_size; i++) {
        ret += visit[home[i].first][home[i].second];
    }
    cout << endl;
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << visit[i][j]<<" ";
        }
        cout << endl;
    }
    */
    cout << Min;
    return 0;
}