[ 삼성 SW역량 평가 15686 ] 치킨 배달 (C++)

[ 관련 지식 ]

1. 조합 https://yabmoons.tistory.com/99

 

[ 난이도 ]

★☆☆

 

[ 문제 링크 ]

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

 

[ 문제 풀이 ]

해당 문제는 Brute Force로 원하는 치킨집의 조합을 모두 탐색하는 것이다.

위 관련 지식에 있는 조합 구현식만 알고 있다면 크게 어려운 부분은 없는 것 같다.

본인은 조합을 구현하는 방법을 몰라서 많이 헤매다가 결국 문제를 해결하였다.

 

 

// 헤더 파일을 불러옵니다.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
// 맵의 최대 크기와 치킨집의 최대 갯수를 선언합니다.
#define Max_Size 51
#define Max_Chicken 13
 
// 맵을 선언합니다.
int Map[Max_Size][Max_Size];
 
// 조합을 사용할 때 사용 되는 변수입니다. 관련지식링크를 참조.
bool Select[Max_Chicken];
 
// 맵의크기와 골라야 하는 치킨집의 개수
int N, M;
 
// 정답을 초기화 시킵니다.
int Answer = 999999;
 
// 치킨집의 개수
int Number_Chicken;
 
// House : 집, Chicken : 치킨집, V : 조합으로 선별된 치킨집
vector<pair<int, int>> House, Chicken, V;
 
// 입력을 받아옵니다
void Load_Input()
{
    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] == 1)
            {
                House.push_back(make_pair(i, j));
            }
            // 치킨집의 좌표를 벡터에 넣습니다.
            if (Map[i][j] == 2)
            {
                Number_Chicken++;
                Chicken.push_back(make_pair(i, j));
            }
        }
    }
}
 
// 최솟값을 구해주는 함수
int min(int num1, int num2)
{
    if (num1 <= num2) return num1;
    else return num2;
}
 
// 치킨거리를 구하는 역할
int Chicken_Distance()
{    
    int Sum = 0;
    for (int i = 0; i < (int)House.size(); ++i)
    {
        int d = 99999999;
        int H_x = House[i].first;
        int H_y = House[i].second;
 
        for (int j = 0; j < (int)V.size(); ++j)
        {
            int C_x = V[j].first;
            int C_y = V[j].second;
            int Dist = abs(H_x - C_x) + abs(H_y - C_y);
            d = min(d, Dist);
        }
        Sum = Sum + d;
    }
    return Sum;
}
 
// 조합을 구현하고 정답을 계속 갱신해줍니다.
void Combination(int idx, int cnt)
{
    if (cnt == M)
    {
        Answer = min(Answer,Chicken_Distance());
        return;
    }
    for (int i = idx; i < Number_Chicken; ++i)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Chicken[i]);
        Combination(i, cnt + 1);
        Select[i] = false;
        V.pop_back();
    }
}
 
int main()
{
    Load_Input();
    Combination(0,0);    
    cout << Answer;
    return 0;
}