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

백준의 치킨배달(15686) 문제이다.

( 문제 바로가기 )

삼성 SW역량테스트 기출 문제이다.

[ 문제설명 ]

- 맵에 치킨집과 가정집이 있다. 존재하는 치킨집 중에서 M개 만을 선택해서 도시의 치킨 거리가 가장 최소가 되는 값을

  찾아야 하는 문제이다.

- 가정집(x,y)와 치킨집(xx,yy)의 거리는 |x-xx| + |y-yy| 로 나타낼 수 있으며, 이 때 치킨집 M개를 어디어디로 선택해야 하는지를

  구하는 문제이다.

[ 문제풀이 ]

1. 전체 치킨집 중에서 M개를 골라서(조합) 거리를 하나하나 다 측정해보고 값을 갱신해 나가면 되는 완전탐색 문제이다.

2. 먼저 나는, 입력으로 주어지는 가정집(MAP에서 1로 표현)과 치킨집(MAP에서 2로 표현)의 좌표를 Vector를 이용해서 저장했다.

3. 이 후, 조합을 구하는 구현방식을 통해서 M개를 선택하도록 하였다.

  3-1) 조합에 관하여....

      * 왜 이문제는 조합일까?

        - 예를 들어서 도시에 치킨집이 5개가 있고(1번~5번이라고 가정) 그 중에 3개를 선택한다고 해보자.

          (1, 2, 3)번 치킨집이 선택되는 경우와 (2, 3, 1)번 치킨집이 선택되는 경우가 결과가 달라질까? 아니다. (1, 2, 3)번을

          치킨집으로 선택하나, (2, 1, 3)번 혹은 (3, 1, 2)번 등으로 선택하든 결과는 같기 때문에 조합이다.

      * 현재까지 Vector에 치킨집의 좌표를 저장해둔 것 말고는 해놓은게 없는데 조합을 어떻게 구할까?

        - 먼저 본인은 Select[] 라는 1차원 배열을 하나 사용하였다. 이 배열은 위에서 말한대로 치킨집의 번호를 대체하는

          배열이다. 위에서 말한대로 5개의 치킨집과 3개를 선택하는 경우로 해보겠다.

          먼저, 1번 치킨집이 선택된 상태라고 가정해보자. 그럼 이 다음에 1번 치킨집을 또 선택할 수 있나? 아니다. 선택할

          수 없다. 방금 말한 부분을 Select배열을 통해 코드적으로 표현해보면 Select[1] = true이다. 즉, 선택됨을 의미한다.

          이렇게 선택이 됬음을 표시하는 동시에, 또 다른 Vector에 앞에서 저장해둔 치킨집의 좌표를 다시 저장해 주었다.

          이런 방식으로 (1,2,3)번 치킨집에 대해서 결과값을 구했다고 가정해보자. 그렇다면 이 다음은 (1,2,4)번 치킨집을

          구해야한다. 즉, 3번을 선택한 상태에서 취소를 하고 4번을 선택해야한다. 이 부분도 코드로 그대로 구현해보면

          Select[3] = false , Select[4] = true로 만들어주면된다. 물론 동시에 Vector에 있는 3을 빼주기 위해서 pop()하는

          과정이 필요할 것이고, 4번을 다시 push하는 과정이 필요할 것이다.

 

        [ 조합 구현 구체적으로 알아보기(Click) ]

        [ 순열 구현 구체적으로 알아보기(Click) ]

         위에서 말한 방식을 재귀와 반복문을 통해서 쉽게 구현할 수 있다. 자세한 내용은 읽은 내용을 생각하면서 밑에 코드 

        를 참고 하도록 하자.

4. 조합을 모두 구한 후에는, 거리를 구해주었다. 거리를 구하는 것은 어렵지 않다. 앞서 저장해둔 가정집의 좌표를 저장한 Vector를이용해서, 하나의 가정집과, 선택된 모든 치킨집의 거리를 모두 비교해서 가장 최소값을 저장시켜주고, 전체 거리에 더해주면 된다.

   - 최소 거리를 구해야 하므로, 모든 치킨집의 거리를 비교해서 가장 가까운(최소값) 거리를 저장시켜줘야 한다.

     하지만 우리가 구해야 하는 것은 전체 도시의 최소거리이므로, 이 거리를 전체 거리에도 더해준다.

   이후에, 조합이 나올 때 마다, 전체거리의 값을 비교해서 값을 갱신시켜 주면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Chicken_Num, Answer;
int MAP[MAX][MAX];
bool Select[13];
 
vector<pair<int, int>> House, Chicken, V;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    Answer = 99999999;
    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) House.push_back(make_pair(i, j));
            if (MAP[i][j] == 2) Chicken.push_back(make_pair(i, j));
        }
    }
    Chicken_Num = Chicken.size();
}
 
int Calculate_Distance()
{
    int Sum = 0;
    for (int i = 0; i < House.size(); i++)
    {
        int x = House[i].first;
        int y = House[i].second;
        int d = 99999999;
 
        for (int j = 0; j < V.size(); j++)
        {
            int xx = V[j].first;
            int yy = V[j].second;
            int Dist = abs(xx - x) + abs(yy - y);
 
            d = Min(d, Dist);
        }
        Sum = Sum + d;
    }
    return Sum;
}
 
void Select_Chicken(int Idx, int Cnt)
{
    if (Cnt == M)
    {
        Answer = Min(Answer, Calculate_Distance());
        return;
    }
 
    for (int i = Idx; i < Chicken_Num; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Chicken[i]);
        Select_Chicken(i, Cnt + 1);
        Select[i] = false;
        V.pop_back();
    }
}
 
void Solution()
{
    Select_Chicken(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}