1. 조건
- 도시 각 칸 : 빈칸 - 0 / 치킨집 - 1 / 집 - 2
- 치킨거리 : 집이랑 가장 가까운 치킨집의 거리
- 도시의 치킨거리 : 모든 집의 치킨거리의 합
2. 입력
- n : 지도 크기
- m : 살아남은 치킨집
- 지도
3. 출력
- 도시의 치킨거리
4. 알고리즘
1) 폐업에서 살아남은 치킨집 m개를 고른다.
- 치킨집이 1,2,3,4,5 가 있을 때 1,2,3이나 2,3,1이나 3,1,2나 똑같다 -> 조합임
2) 집이랑 치킨집 m개중에서 가장 가까운 치킨거리를 구한다.
3) 모든 집들에 대해 2)를 수행해 도시의 치킨거리를 구한다.
C++)
1. 백트래킹
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define MAX_NUM 52
using namespace std;
int n, m;
vector<pair<int, int>> chicken; // 치킨집 위치
vector<pair<int, int>> house; // 집위치
bool visited[15]; // 치킨집 방문 여부
int surviveChicken[15]; // 폐업 안 하고 살아남은 치킨집
int ans = 987654321;
void func(int cnt, int st) {
// 폐업 안 할 치킨집 m개 골랐으면
if (cnt == m) {
int sum = 0;
// 집과
for (int i = 0; i < house.size(); i++) {
int temp = 987654321;
int r1 = house[i].first;
int c1 = house[i].second;
// 치킨집들 사이의 치킨거리를 구한다
for (int j = 0; j < m; j++) {
int r2 = chicken[surviveChicken[j]].first;
int c2 = chicken[surviveChicken[j]].second;
temp = min(temp, abs(r1 - r2) + abs(c1 - c2));
}
sum += temp;
}
ans = min(ans, sum);
return;
}
// 폐업 안 할 치킨집 구하기
for (int i = st; i < chicken.size(); i++) {
if (!visited[i]) {
surviveChicken[cnt] = i;
visited[i] = true;
func(cnt + 1, i + 1);
visited[i] = false;
}
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
int temp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> temp;
// 집
if (temp == 1)
house.push_back({ i,j });
// 치킨집
else if (temp == 2)
chicken.push_back({ i,j });
}
}
func(0, 0);
cout << ans << "\n";
return 0;
}
2. next_permutation
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define MAX_NUM 52
using namespace std;
int n, m;
vector<pair<int, int>> chicken; // 치킨집 위치
vector<int> surviveChicken; // 치킨집 조합 구해야함
vector<pair<int, int>> house; // 집 위치
int func(vector<int>& survivor) {
int sum = 0;
// 집과
for (int i = 0; i < house.size(); i++) {
int r1 = house[i].first;
int c1 = house[i].second;
int temp = 987654321;
// 살아남은 치킨집들 중에서 가장 가까운 치킨집과의 거리 구함
for (auto pos : survivor) {
int r2 = chicken[pos].first;
int c2 = chicken[pos].second;
temp = min(temp, abs(r1 - r2) + abs(c1 - c2));
}
sum += temp;
}
return sum;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
int temp;
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> temp;
if (temp == 1)
house.push_back({ i,j });
else if (temp == 2) {
surviveChicken.push_back(chicken.size() < m ? 0 : 1);
chicken.push_back({ i,j });
}
}
}
int ans = 987654321;
// 조합 구하기
do {
int sum = 0;
vector<int> survivor;
for (int i = 0; i < chicken.size(); i++) {
if (surviveChicken[i] == 0) // 선택된 치킨집
survivor.push_back(i);
}
ans = min(ans, func(survivor));
} while (next_permutation(surviveChicken.begin(), surviveChicken.end()));
cout << ans << "\n";
return 0;
}
next_permutation 구할 때
- 살아남은 치킨집 하나 구하고 집들과 거리 구하는게 아니라
- 살아남은 치킨집들 전부 구하고 집과의 거리 구해야함
Python)
1. 백트래킹
import sys
read = sys.stdin.readline
houses = [] # 집들 위치
chicken = [] # 치킨집 위치
visited = [False] * 15 # 치킨집 폐업 여부 저장
survivors = [] # 치킨집 최대 13개
ans = 987654321 # 도시의 치킨거리
n, m = map(int, read().rstrip().split())
for i in range(n):
temp = list(read().rstrip().split())
# 입력 받으면서 집과 치킨집 위치 구하기
for j in range(n):
if temp[j] == '1':
houses.append((i,j))
elif temp[j] == '2':
chicken.append((i,j))
def func(cnt, idx):
global ans
# 폐업할 치킨집을 m개 골랐으니 각 집들의 치킨 거리를 구한다.
if cnt == m:
sum = 0
# 각 집들의
for house in houses:
r1, c1 = house[0], house[1]
temp = 987654321
# 치킨거리를 구해서
for r2, c2 in survivors:
temp = min(temp, abs(r2-r1)+abs(c2-c1))
# 도시의 치킨거리를 구한다
sum += temp
ans = min(ans, sum)
return
for i in range(idx, len(chicken)):
if not visited[i]:
survivors.append(chicken[i])
visited[i] = True
func(cnt+1, i+1)
visited[i] = False
survivors.pop()
func(0, 0)
print(ans)
2. from itertools import combinations
import sys
from itertools import combinations
read = sys.stdin.readline
arr = [] # 지도
houses = [] # 집들 위치
chicken = [] # 치킨집 위치
n, m = map(int, read().rstrip().split())
ans = 987654321 # 도시의 치킨거리
for i in range(n):
arr.append(list(read().rstrip().split()))
# 입력 받으면서 집과 치킨집 위치 구하기
for j in range(n):
if arr[i][j] == '1':
houses.append([i,j])
elif arr[i][j] == '2':
chicken.append([i,j])
for survivors in list(combinations(chicken, m)):
sum = 0
# 각 집들의
for house in houses:
r1, c1 = house[0], house[1]
temp = 987654321
# 치킨거리를 구해서
for survivor in survivors:
r2, c2 = survivor[0], survivor[1]
temp = min(temp, abs(r2-r1)+abs(c2-c1))
# 도시의 치킨거리를 구한다
sum += temp
ans = min(ans, sum)
print(ans)
c++ next_permutation 보다 직관적이어서 좋다.
시간은 1번처럼 백트래킹으로 푼 풀이가 2배 정도 더 빨랐음.
'백준 2 > 백트래킹' 카테고리의 다른 글
| [백준 15664] N과 M (10) (C++/Python) (0) | 2023.07.29 |
|---|---|
| [백준 15663] N과 M (9) (C++/Python) (0) | 2023.07.28 |
| [백준 1759] 암호 만들기 (C++/Python) (0) | 2020.12.07 |
| [백준 6603] 로또 (C++/Python) (0) | 2020.12.07 |
| [백준 1987] 알파벳 (0) | 2020.12.07 |