15686번 치킨 배달

문제 링크 : https://www.acmicpc.net/problem/15686

해결 방법)

풀고나서 다른 해결방법들을 보니까 대게 비슷하게 푼것같다. 

그래도 내가 푼 아이디어를 풀어보고자 한다. (누군가에게는 도움이 되겟지하는 생각에)

치킨집 고르는 경우 즉 M개(1개의 치킨집, 2개의 치킨집, 3개의 치킨집 ...... M개의 치킨집) 에서 모든 집들과의 거리중 최소거리만 구하여 이 최소거리의 합들이 우리가 구하고자하는 도시의 치킨거리값이 되는 것이다.

그런데 우리는 1개를 어떻게고르고 2개를 어떻게고르고에 대한 아이디어가 없당 ㅜ 이것은 재귀적으로 상황을 두개 만들어 주면 된다. 있고, 없고의 두가지상황인데 A,B,C의 치킨집이있다고하면,

A 있고 B 있고, C 없고

A 없고 B 있고 C 없고 .... 요론식으로 하다보면 모든 경우의수를 찾을 수 있다는 느낌을 받을 수 있다.

즉 각 치킨집마다 있고 없고의 상황 두가지를 만들어서 치킨집을 먼저 고를 수 있다.

이제 골라진 치킨집이 1개일때,2개일때 ,3개일때, 4개일때..... M개 이하 일때 마다 치킨 거리 총합을 알아야지 도시의 치킨거리를 알 수 가있는데 어떻게 골라진 치킨집 개수마다 그 치킨거리 총합을 알아낼 것인가가 문제이다.

이 해결방법은 모든 집마다 거리를 구하는데 골라진 집들과의 사이를 구하면서 최소값을 각 집마다 구해나가는 것이다.

우리는 각치킨집마다 경우를 있고,없고의 두가지 경우를 만들었는데, 이때 치킨집이 있다라면 이 치킨집은 골라진녀석이고 따로 골라졌다라는 표식을 남겨두면 나중에 골라진 치킨집에대해 거리값을 구해나갈수 있다.

따라서 골라진 치킨집과 모든 집들사이의 거리를 구할 수 있게되고 당연히 최소값도 구하게되면서 이 최소값들의 총합이 결국엔 우리가 구하는 답이 된다.

또 참고로 최대 M개라고해서 M개를 골랐을때만 왜 조건을 거냐라고 말할 수 있는데, 어차피 FOR문을 돌면 각집이 치킨집들 중 최소값만 지니기 때문에 하나의 치킨집만 선택된경우도 자연스레 포함이 되어 모든 경우를 내포하기때문이다.

소스코드)

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int ans = 987654321; // 도시의 치킨거리
int M;
int visit[13];
vector<pair<int, int>> home; // 집좌표
vector<pair<int, int>> chicken; // 치킨 좌표
int csize;
int min(int a, int b) { return a < b ? a : b; }
void solve(int inow, int cnt_now)
{
    if (cnt_now == M) // 최대 M개를 고를때
    {
        int d; // 두점사이의 거리
        int x1, x2;
        int y1, y2;
        int tmp = 0;
        int homesize = home.size();
        for (int i = 0; i < homesize; i++)
        {
            int minnum = 987654321;
            for (int j = 0; j < csize; j++)
            {
                if (visit[j]) 
                {
                    d = abs(home[i].first - chicken[j].first) + abs(home[i].second - chicken[j].second);
                    if (minnum > d)
                        minnum = d;
                }
            }
            tmp += minnum;
            
        }
        ans = min(ans, tmp); //도시치킨거리 갱신
        return;
    }
    if (inow >= csize) return; 
    visit[inow] = 1;// 현재 치킨집 선택
    solve(inow + 1, cnt_now + 1); 
    visit[inow] = 0; 
    solve(inow + 1, cnt_now);
}
int main()
{
    int N;
    int num;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            scanf("%d", &num);
            if (num == 1)
            {
                home.push_back({ i,j });
            }
            else if (num == 2)
            {
                chicken.push_back({ i,j });
            }
        }
    }
    csize = chicken.size();
    solve(0, 0);
    printf("%d\n",ans);
}