CS/알고리즘
백준 15686번: 치킨 배달
신정훈
2024. 2. 20. 02:00
https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
문제 접근
완전 탐색 + 접근 문제이다.
입력값으로 주어지는 M개의 치킨 집을 골라야 한다.
치킨 거리 = 집에서 가장 가까운 치킨 집의 거리
도시의 치킨 거리 = 치킨거리의 합
M개의 치킨집을 조합한뒤
조합과 집의 좌표를 비교해
가장 가장 가까운 치킨 집을 찾는다.
각집의 치킨 거리를 모두 더해
도시의 치킨 거리를 구한다.
각 조합에 대한 도시의 치킨 거리를 비교해
가장 작은 값을 구한다.
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <cstring>
#include <stack>
using namespace std;
int N, M;
int arr[51][51] = {};
vector<vector<int>> chickenList;
vector<pair<int, int>> chickenPos;
vector<pair<int, int>> housePos;
void combi(int start, vector<int> v)
{
if (v.size() == M)
{
chickenList.push_back(v);
return;
}
for (int i = start + 1; i < chickenPos.size(); i++)
{
v.push_back(i);
combi(i, v);
v.pop_back();
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> arr[i][j];
if (arr[i][j] == 1)
housePos.push_back({ i,j });
if (arr[i][j] == 2)
chickenPos.push_back({ i,j });
}
}
int ans = 1e9;
vector<int> v;
combi(-1, v);
for (int i = 0; i < chickenList.size(); i++)
{
// 도시의 치킨 거리 = 치킨 거리들의 합
int ret = 0;
for (int j = 0; j < housePos.size(); j++)
{
// 치킨 거리 = 집과 가장 가까운 치킨집과의 거리
int mn = 1e9;
for (auto ch : chickenList[i])
{
int dist = abs(housePos[j].first - chickenPos[ch].first) + abs(housePos[j].second - chickenPos[ch].second);
mn = min(mn, dist);
}
ret += mn;
}
ans = min(ans, ret);
}
cout << ans;
}