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

문제 설명

https://www.acmicpc.net/problem/15686
크기가 N×N인 도시에 0은 빈 칸, 1은 집, 2는 치킨집으로 구성된다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이고, 도시의 치킨 거리는 모든 집의 치킨 거리의 합을 말한다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 입력으로 주어지고 둘째 줄부터 도시의 정보가 주어진다.
도시에 있는 치킨집 중에서 M개만 남기고 나머지 치킨집은 모두 폐업시켜야 할 때 최소 도시의 치킨 거리를 구하는 문제다.

아이디어

1. m개의 치킨집 고르기(조합)
2. 각 집에서 해당 조합의 치킨집까지 최단거리 구하기

조합은 next_permutation을 활용하여 구현하였다. 참고블로그
1) 뽑아야 하는 개수 m개만큼 1을 넣고 전체 개수-m개 만큼 0을 넣은 벡터comb를 만든다.(오름차순정렬)
2) do while문 안에 for문을 통해 comb[i]의 값이 1이면 조합요소로 선택된다.
3) next_permutation(comb.begin(), comb.end())로 재정렬

각 집에서 치킨집까지의 최단거리를 bfs로 풀었는데 시간초과가 났다. bfs 필요없이 바로 거리를 구할 수 있었다.못지나가는 구역이 있으면 bfs를 사용하는 건데 모든 구역(치킨집, 집)을 다 지날 수 있기 때문에 출발,도착 좌표만 안다면 거리를 구할 수 있었다.
생각해보면 문제에 힌트가 있었다...

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, c_total;
int a[51][51];
vector<pair<int, int>> chicken;
vector<int> comb, v;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 2)
            {
                chicken.push_back({i, j}); //치킨집 위치 저장
                c_total++;
            }
        }
    }

    for (int i = 0; i < c_total - m; i++)
    {
        comb.push_back(0);
    }
    for (int i = 0; i < m; i++)
    {
        comb.push_back(1);
    }

    do
    {
        vector<pair<int, int>> b;
        for (int i = 0; i < comb.size(); i++)
        {
            if (comb[i] == 1)
            {
                b.push_back({chicken[i].first, chicken[i].second});
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (a[i][j] == 1)
                {
                    int dist = 100;
                    for (int k = 0; k < m; k++)
                    {
                        int tmp = abs(i - b[k].first) + abs(j - b[k].second);
                        dist = min(dist, tmp);
                    }
                    res += dist;
                }
            }
        }
        v.push_back(res);
    } while (next_permutation(comb.begin(), comb.end()));

    sort(v.begin(), v.end());
    cout << v[0] << "\n";
}