[백준] 15686번
💻 C++ 기반
// 시간 복잡도: 13 * 100 * 13C6 = 2,230,800
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#define MAX 51
#define MAX_DIST 98765
using namespace std;
int N, M;
int city[MAX][MAX];
vector<pair<int, int> > homes;
vector<pair<int, int> > chickens;
int getDistToChicken(int startY, int startX, vector<int> selected)
{
int result = MAX_DIST;
for (int i = 0; i < M; i++)
{
int chickenY = chickens[selected[i]].first;
int chickenX = chickens[selected[i]].second;
result = min(result, abs(startY - chickenY) + abs(startX - chickenX));
}
return result;
}
int main()
{
scanf("%d %d", &N, &M);
int cntOfChickens = 0; // 총 치킨집의 수
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
scanf("%d", &city[i][j]);
if (city[i][j] == 1)
{
homes.push_back(make_pair(i, j));
}
else if (city[i][j] == 2)
{
chickens.push_back(make_pair(i, j));
cntOfChickens++;
}
}
}
vector<int> temp;
for (int i = 0; i < M; i++)
{
temp.push_back(0);
}
for (int i = M; i < cntOfChickens; i++)
{
temp.push_back(1);
}
int ans = MAX_DIST;
do
{
vector<int> selected;
for (int i = 0; i < cntOfChickens; i++)
{
if (temp[i] == 0)
{
selected.push_back(i);
}
}
int dist = 0;
for (int i = 0; i < homes.size(); i++)
{
dist += getDistToChicken(homes[i].first, homes[i].second, selected);
}
ans = min(ans, dist);
} while (next_permutation(temp.begin(), temp.end()));
printf("%d", ans);
return 0;
}
Author And Source
이 문제에 관하여([백준] 15686번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jieun_han/백준-15686번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)