치킨 배달 C++ 골드 5 (코드 재밌어서 공유)

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

생각의 흐름

1.최대 M개를 고르라는 말의 의미는 무엇이지?
=> 최대 M개를 안 고르는 경우도 있나?

2. 치킨집을 제거한다고 하는 경우, 다른 치킨집의 거리에 영향이 가는가?
=> 좌표로 계산하기 때문에 영향이 없음.

=> 1번은 모르겠으나, 2번의 특성을 본다면, 모든 경우의 수를 탐색해서 계산하면 그만이겠다는 생각이 들었다.
=> 조금 느릴 것 같은데, 빠르게 하는 방법은 없을까? => 그리디?
근데 N이 50이라 워낙 수가 작아서 총 칸이 250이고, 집은 커봐야 2N이라 100 밖에 안 된다는 생각에 모든 경우의 수를 구하려고 했다.

=> 마음에 걸리는 요소는 1번, M개 이건 뭐지?

조합.. 😑 👍

조합을 구현하고, 계산의 요소를 추가한 문제로 보인다.

조합은 어떻게 구한? 개수를 지정한 백트래킹이고, 해당 코드에 계산 요소만 가미하면 된다.

코드를 이쁘게 쓰려고 했지만, 변수명은 별로라.. 그래도 신경쓴 부분을 아래 적어본다.

enum State { EMPTY, HOUSE, CHICKEN }; =>  이넘을 이용해서 숫자를 0, 1, 2를 문자열로 나타내봄
int answer = INT_MAX; =>  climits 라이브러리 이용해서 사용해봄.

visited[r][c] = true; selected.push_back({ r, c }); 이런식으로 코드의 줄을 줄여보려고 노력해봄 🔥

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

// 2<=n<=50, 1 <= m <= 13
int n, m;
int board[50][50];
bool visited[50][50];
enum State { EMPTY, HOUSE, CHICKEN };

vector<pair<int, int>> chickens;
vector<pair<int, int>> houses;
vector<pair<int, int>> selected;
int answer = INT_MAX;

void calculate() {
    int distance = 0;
    for(int i=0; i<houses.size(); i++) {
        int minDistance = INT_MAX;
        for(int j=0; j<selected.size(); j++) {
            minDistance = min(minDistance, abs(houses[i].first - selected[j].first) + abs(houses[i].second - selected[j].second));
        }
        distance += minDistance;
    }
    answer = min(answer, distance);
}

void combination(int index, int count) {
    if(count == m) { calculate(); return; }
    
    for(int i=index; i<chickens.size(); i++) {
        int r = chickens[i].first; int c = chickens[i].second;
        if(visited[r][c]) {
            continue;
        }
        
        visited[r][c] = true; selected.push_back({ r, c });
        combination(i, count + 1);
        visited[r][c] = false; selected.pop_back(); 
    }
}

int main() {
    cin >> n >> m;
    
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) {
        cin >> board[i][j];
        if(board[i][j] == HOUSE) houses.push_back({ i, j });
        if(board[i][j] == CHICKEN) chickens.push_back({ i, j });
    }
    
    combination(0, 0);
    cout << answer;
}