난이도 : 골V
풀이 시간 : 40분
알고리즘 유형 : 백트래킹, 조합(Comb)
풀이 방법 : (백트래킹, 조합) 을 이용한 최소 거리 합 계산
문제 링크
https://www.acmicpc.net/problem/15686
문제 예시
주어진 N×N 크기의 도시에서, 각 칸은 빈 칸(0), 집(1), 치킨집(2)으로 구분됩니다.
각 집은 가장 가까운 치킨집과의 거리를 계산해 "치킨 거리"를 가집니다.
도시의 "치킨 거리"는 모든 집의 치킨 거리 합입니다.
(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2,
(5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다.
따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.
(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6,
(5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다.
따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.
이제 치킨집 중 최대 M개를 고르고 나머지는 폐업시키려 합니다.
목표는 선택한 치킨집들에 대해 도시의 치킨 거리가 최소가 되도록 하는 것입니다.
문제 풀이 방식
이 문제는 N×N 크기의 도시에서 치킨 거리를 최소화하는 방법을 찾는 문제입니다.
도시의 각 칸은 빈 칸(0), 집(1), 치킨집(2)으로 구분됩니다.
각 집은 가장 가까운 치킨집과의 거리를 계산하여 치킨 거리를 구하며,
도시는 모든 집들의 치킨 거리 합으로 정의됩니다.
문제의 핵심은 주어진 치킨집 중 최대 M개를 선택하여,
선택된 치킨집들만 운영하고 나머지는 폐업시키는 것입니다.
이때 치킨 거리가 최소가 되도록 치킨집을 선택하는 방법을 찾아야 합니다.
- 집과 치킨집의 좌표 파악: 주어진 도시에서 집(1)과 치킨집(2)의 좌표를 모두 추출합니다.
- 치킨집 선택: 최대 M개까지 치킨집을 선택해야 하므로, 가능한 치킨집 조합을 모두 구합니다.
- 치킨 거리 계산: 각 집에 대해 선택된 치킨집들 중 가장 가까운 치킨집과의 거리를 계산하고, 그 합을 구합니다.
- 최소 치킨 거리: 모든 가능한 조합에 대해 치킨 거리의 최솟값을 구합니다.
주요 아이디어
- 조합을 이용해 가능한 치킨집 선택을 하고, 각 선택에 대해 치킨 거리를 계산합니다.
- 집과 치킨집 간의 거리는 맨해튼 거리(|r1-r2| + |c1-c2|)로 계산됩니다.
백트래킹을 이용해서 이 문제를 푸는 게 정석이긴 하지만
순열을 이용해 풀 수도 있습니다.
결국 해당 조합을 모두 확인하기 때문입니다.
풀이는 백트래킹과 순열을 모두 풀어봤습니다.
아래는 백트래킹을 이용한 코드입니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, answer = 2e9;
int cities[51][51];
vector<pair<int, int>> chiken;
vector<pair<int, int>> home;
vector<pair<int, int>> Points;
int calc_value()
{
int sum = 0;
// 집의 위치를 확인한다.
for (int i = 0; i < home.size(); ++i)
{
int mn = 2e9;
// 치킨집과 집 위치 최솟값을 주어잔 형태로 찾는다.
for (int j = 0; j < Points.size(); ++j)
{
int x = abs(Points[j].first - home[i].first);
int y = abs(Points[j].second - home[i].second);
mn = min(mn, x + y);
}
sum += mn;
}
return sum;
}
void dfs(int idx)
{
// 사이즈가 같아졌을 때 계산한다.
if (Points.size() == m)
{
answer = min(answer, calc_value());
return;
}
// 백트래킹을 수행하고 위치를 저장시켜준다.
for (int i = idx; i < chiken.size(); ++i)
{
Points.push_back(chiken[i]);
dfs(i + 1);
Points.pop_back();
}
}
int main()
{
ios::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 >> cities[i][j];
// 치킨집과 집을 저장해놓는다.
if(cities[i][j] == 2)
chiken.push_back({i, j});
else if(cities[i][j] == 1)
home.push_back({i, j});
}
}
dfs(0);
cout << answer;
return 0;
}
아래는 순열을 이용한 코드입니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
int board[52][52];
int answer = 2e9;
// 0 빈칸
// 1 집
// 2 치킨집
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;
int main(void) {
ios::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 >> board[i][j];
if(board[i][j] == 2)
chicken.push_back({i, j});
else if(board[i][j] == 1)
home.push_back({i, j});
}
}
vector<int> permutation(chicken.size(), 1);
// 치킨집 - m으로 순열을 돌릴 조합을 갱신한다.(0을 채워야 순열이 돌아가기 때문)
fill(permutation.begin(), permutation.begin() + chicken.size() - m, 0);
do
{
int dist = 0;
for (auto h : home)
{
int mn = 2e9;
// 위에 Calc 함수와 비슷하게 계산해준다.
for (int i = 0; i < chicken.size(); ++i)
{
int cur = abs(chicken[i].first - h.first) +
abs(chicken[i].second - h.second);
if (permutation[i])
mn = min(mn, cur);
}
dist += tmp;
}
answer = min(dist, answer);
} while(next_permutation(permutation.begin(), permutation.end()));
cout << answer;
}