[백준 15686][C++] 치킨 배달

 

문제 링크

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

---

◆문제 해결 및 설명◆

문제 :  N개의 치킨집만 남기고 폐업 시에, 각각의 치킨집과 집의 거리의 합들을 최소화하는 상황의 거리의 합을 구하여라.

 

우선 알고리즘적으로 생각나는것은 없었고, 조합을 통한 거리 계산이라는 문제임을 깨달았다.

문제는 C++로 조합을 만들 줄 모른다는것...

그래서 다른 분의 포스팅을 참고 하였다.

https://ansohxxn.github.io/algorithm/combination/

(C++) 조합(Combination) 구현하기

(좋은 블로그라 이후에도 많이 배워야 겠다.)

 

Pair<>를 통해 치킨 집과 집의 좌표를 저장해주고

반복문을 통해서 각각 모든 집과 치킨집의 거리를 계산해서 chickenLen이라는 이차원 배열에 넣었다.

chickenLen[집][치킨집] = 거리

 

이후에 재귀를 통한 Combination함수를 통해 구할 수 있는 조합을 combination 이차원 배열에 넣어주었다.

combination[i] = 순열의 배열

• ex) combination[0]=(1,2,3) , combination[1]=(1,2,4) , combination[2]=(1,3,4)

 

마지막으로 Calculate 함수를 이용하여 (순열에 해당하는 치킨집과 집의 거리 중 최단거리들을 각각 합쳐서) 제일 작다면 정답으로 설정해 주었다.

※여담으로 INT_MAX를 위해 #include <climits>를 추가 해주는것을 알게 되었다.

◆코드 전문◆

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
// 치킨집의 좌표
vector<pair<int, int>> chicken;
// 집의 좌표
vector<pair<int, int>> house;
// 순열의 종류
vector<vector<int>> combination;

// 입력 받을 변수들
int N, chikenLiveCount;
// 정답
int answer = INT_MAX;

// chickenLen에 house에 모든 chicken의 거리를 계산하여 배열로 저장한다.
void Distance(vector<vector<int>> &chickenLen)
{
    for (int i = 0; i < house.size(); i++)
    {
        for (int k = 0; k < chicken.size(); k++)
        {
            int buf = abs(house[i].first - chicken[k].first) + abs(house[i].second - chicken[k].second);
            chickenLen[i][k] = buf;
        }
    }
    return;
}

// 매개변수 comb 배열을 통해 조합을 만들고 combination배열에 삽입해 준다.
void Combination(int size, int index, int depth, vector<int> comb)
{
    if (depth == chikenLiveCount)
    {
        combination.emplace_back(comb);
        return;
    }
    else
    {
        for (int i = index; i < size; i++)
        {
            comb[depth] = i;
            Combination(size, i + 1, depth + 1, comb);
        }
    }
}

// chickenLen 이차원 배열에서 순열마다 도시의 치킨 거리를 계산하여 비교한다.
void Calculate(vector<vector<int>> &chickenLen)
{
    int buf;
    for (int i = 0; i < combination.size(); i++)
    {
        int minCal = 0;
        for (int k = 0; k < chickenLen.size(); k++)
        {
            buf = chickenLen[k][combination[i][0]];
            for (int x = 0; x < combination[i].size(); x++)
            {
                buf = min(chickenLen[k][combination[i][x]], buf);
            }

            minCal += buf;
        }
        if (minCal < answer)
        {
            answer = minCal;
        }
    }
}

int main()
{

    cin >> N >> chikenLiveCount;
    vector<vector<int>> mapArray(N + 1);
    for (int i = 0; i <= N; i++)
    {
        if (i == 0)
        {
            for (int k = 0; k <= N; k++)
            {
                //(0,~),(~,0)을 9로 채워줌
                mapArray[i].emplace_back(9);
            }
        }
        mapArray[i].emplace_back(9);
    }

    for (int i = 1; i <= N; i++)
    {
        for (int k = 1; k <= N; k++)
        {
            int a;
            cin >> a;
            mapArray[i].emplace_back(a);
            if (a == 2)
            {
                chicken.emplace_back(make_pair(i, k));
            }
            else if (a == 1)
            {
                house.emplace_back(make_pair(i, k));
            }
        }
    }

    // 치킨집과의 거리
    vector<vector<int>> chickenLen(house.size(), vector<int>(chicken.size(), 0));

    Distance(chickenLen);

    vector<int> comb(chikenLiveCount);
    Combination(chicken.size(), 0, 0, comb);

    Calculate(chickenLen);

    cout << answer;
}

 

치킨이 먹고싶은 날이다.