15686.치킨배달

이번에는 오랜만에 백준의 문제를 풀어보았다. 15686 치킨배달이라는 문제이고 재귀함수

조합에 대한 공부를 하기 좋은 문제 같다. 난이도나 유형은 이전의 요리사와 상당히 비슷한 문제같이 느껴진다.

15686번: 치킨 배달

다행이 풀어내는데 성공했고 풀어내면서 느낀점은 설계의 중요성이다. 재귀함수를 두 번 진행했기에

설계를 잘못하면 너무 복잡해지므로 꼭 설계가 끝나기전까지는 코딩하지말자!!

 

 

---

 

이 문제의 풀이 과정은 다음과 같다.

 

1. 치킨의 좌표들 중에 M개를 선택하는 로직

=> 즉, 조합을 구현해야한다.

 

2. 선택한 M개의 치킨좌표와 집 좌표와의 치킨거리를 구하기 

=> 이 때 최소값을 선택해야한다. 이렇게 구하게되면 최소값은 모두 집 좌표의 개수 만큼 나오게 된다.

=> 그걸 전부 더한것이 정답의 치킨거리라고 하였으니 정답의 치킨거리를 저장해놓고 최소값을 찾으면 된다.

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <algorithm>
 
#define MAX 51
 
using namespace std;
 
int N, M;
int map[MAX][MAX]; // 집과 치킨 맵
bool check[MAX];   // 조합에 사용될 배열
bool flag;         // 재귀종료 플레그
 
deque<pair<int, int>> h; // home의 좌표
deque<pair<int, int>> c; // chicken 좌표
deque<pair<int, int>> t; // chicken 좌표 중 선택한 M개의 좌표 조합
 
int tmp, sum, ans; // 치킨거리 저장변수, 치킨거리들의 합 변수, 정답 변수
 
int length(int a, int b){ // 치킨거리를 구하는 함수
    int x = abs(h[a].first - t[b].first);
    int y = abs(h[a].second - t[b].second);
    return x + y;
}
 
// 치킨좌표의 총 개수 중 M개의 조합을 이용하여 집과 치킨집의 치킨거리를 구하는 함수
void search(int idx1, int idx2){ // idx1 = home의 idx, idx2 = chicken 좌표 중 선택한 M의 idx  
    if (flag) // 재귀 종료 플래그가 참이면
        return; // 계속 리턴
 
    if (idx1 == h.size()){     // idx1의 값이 home의 좌표갯수만큼 되면 탐색을 다했다는 의미이므로
        ans = min(ans, sum);   // 최소값을 저장함
        sum = 0;               // 합산값 초기화
        flag = true;           // 재귀 종료 플래그 활성화
        return;      
    }
 
    if (idx2 == t.size()){     // chicken 좌표 중 선택한 M개의 갯수만큼 idx2가 진행되었다면
        sum += tmp;            // 해당 home에서의 치킨거리를 더해주고
        tmp = 987654321;       // 임시 비교 변수 초기화
        return;
    }
 
    tmp = min(tmp, length(idx1, idx2)); // 치킨거리를 구하여 tmp 변수에 저장
 
    search(idx1, idx2 + 1); // 다음 재귀함수 진행 => 다음 치킨 idx로 치킨거리 탐색
    search(idx1 + 1, 0);    // 치킨 idx를 끝까지 탐색했다면 다음 home 좌표로 다시 치킨좌표idx를 0부터 진행
 
}
 
// 치킨좌표의 총 개수와 M개의 조합을 만들어 내는 함수
void choice(int start, int cnt){
 
    if (cnt == M){ // 선택한 개수가 M가 되었다면
        for (int i = 0; i < c.size(); i++)
            if (check[i])
                t.push_back(make_pair(c[i].first, c[i].second)); // 선택된 좌표 따로 저장
 
        search(0, 0); // 선택된 좌표들과 집과의 치킨거리 구함
        t.clear();    // 다 구했으면 선택한 좌표 초기화
        flag = false; // 탐색종료 플래그 비활성
        return;
    }
 
    for (int i = start; i < c.size(); i++){ // 치킨 idx로 조합 진행 => 시작점을 잘 지정해준다.
        if (!check[i]){      // 선택안했다면
            check[i] = true; // 선택
            choice(i, cnt + 1); // 다음 선택 진행
            check[i] = false;// 다음 조합을 위해 false
        }
    }
 
}
 
int main() {
    //freopen("15686.txt", "r", stdin);
    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) 
                h.push_back(make_pair(i, j)); // 집좌표 따로저장
            else if (map[i][j] == 2)
                c.push_back(make_pair(i, j)); // 치킨집 좌표 따로 저장
        }
    }
    ans = tmp = 987654321; // 정답과 치킨거리 변수 초기화
    sum = 0;               // 치킨거리의 합 변수 초기화
    choice(0,0);           // 치킨좌표 조합 함수 진행
    cout << ans << endl;  
    return 0;
}