#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, res = 2147000000, sum = 0;
int a[50][50];
int ch[50];
vector<pair<int, int>> house;
vector<pair<int, int>> pizza;
void DFS(int s, int L)
{
if(L == m) // 피자집 m개를 뽑았으면
{
sum = 0;
for(int i = 0; i < house.size(); i++)
{
int x1 = house[i].first; // 피자집과의 거리를 비교할 집의 x좌표
int y1 = house[i].second; // 피자집과의 거리를 비교할 집의 y좌표
int dis = 2147000000; // 비교할 거리
for(int j = 0; j < m; j++)
{
int x2 = pizza[ch[j]].first;
int y2 = pizza[ch[j]].second;
dis = min(dis, abs(x1 - x2) + abs(y1 - y2)); // dis와 수식 중 더 작은 값을 return
}
sum += dis; // 도시의 피자 배달거리에 더하기
}
if(res > sum) res = sum;
}
else
{
for(int i = s; i < pizza.size(); i++)
{
ch[L] = i; //pizza 집 개수 중에서 m개 숫자 뽑는 방법. L 번째 숫자에 숫자 i를 두겠다.
DFS(i+1, L+1); // 0-3까지 넣었다면 다음은 3을 제외한 0-4까지, 0-5까지,,
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
if(a[i][j] == 1)
{
house.push_back(make_pair(i, j)); // 집 위치 저장
}
else if(a[i][j] == 2)
{
pizza.push_back(make_pair(i, j)); // 피자집 위치 저장
}
}
DFS(0, 0);
printf("%d", res);
return 0;
}
- a개의 숫자 중에서 b개의 숫자를 뽑는 DFS를 알아야한다. 아주 간단하게 표현할 수 있다.
#include <stdio.h>
int a, b;
int ch[30];
void DFS(int s, int L) // s는 else 문 내 for에서 시작점을, L은 트리의 깊이다.(뽑은 숫자의 개수)
{
if(L == b)
{
// 뽑고나서 할 로직
}
else
{
for(int i = s; i < a; i++) // DFS(0,0) s = 0
{
ch[L] = i; // ch[0] = 0
DFS(i+1, L+1); // DFS(1, 1)
}
}
}
int main()
{
scanf("%d %d", &a, &b);
DFS(0,0)
return 0;
}1. a = 6, b = 4 라고 해보겠다. DFS(0, 0)부터 시작한다.
- DFS(0, 0)
- L = 0 이므로 else 문 내의 for로 간다. s = 0 이므로 ch[L] = ch[0] = i = 0; DFS(1, 1);
- DFS(1, 1)
- L = 1 이므로 else 문 내의 for로 간다. s = 1 이므로 ch[L] = ch[1] = i = 1; DFS(2, 2);
- DFS(2, 2)
- L = 2 이므로 else 문 내의 for로 간다. s = 2 이므로 ch[L] = ch[2] = i = 2; DFS(3, 3);
- DFS(3, 3)
- L = 3 이므로 else 문 내의 for로 간다. s = 3 이므로 ch[L] = ch[2] = i = 3; DFS(4, 4);
- DFS(4, 4)
- L = 4 이므로 if 문 내 로직으로 이동한다.
여기까지의 ch 배열을 표현해보겠다.
| 0 | 1 | 2 | 3 |
위 코드의 진행에서 마지막이 DFS(4, 4)였다. 여기서 if 문 내 로직이 끝나면 DFS(3 ,3)으로 돌아간다. DFS(3, 3)에서 for문을 다시 돌게 된다.
- DFS(3, 3)
- L = 3 이므로 else 문 내의 for로 간다. s = 3 이지만 i = 4이므로 ch[L] = ch[2] = i = 4; DFS(4, 4);
여기까지의 ch 배열을 표현해보겠다.
| 0 | 1 | 2 | 4 |
이렇게 반복하면 6개 숫자(0-5) 중에서 4개를 뽑는 모든 경우의 수가 나오게 된다.
- 6개의 피자집 위치를 담은 vector를 선언한다. 이 때 위치는 2차원 좌표이므로 pair<int, int> 형의 vector를 선언
- 5개의 집이 있다. 집의 위치를 담은 vector를 피자집과 같이 pair<int, int> 형으로 선언한다.
- 6개의 피자집 중 4개를 남기려고한다. 4개를 뽑는다는 의미이다.
- 피자집은 피자집1, 피자집2 ... 피자집6으로 정하고 각 숫자는 인덱스이다. 먼저 임의의 피자집 4개를 뽑는다. 처음은 피자집1, 피자집2, 피자집3, 피자집4가 될 것이다. 이 인덱스를 ch 배열에 담는다.
- 집은 집1부터 집5까지 있을 것이다. 집1부터 피자집1, 피자집2, 피자집3, 피자집4 와의 거리를 계산하고 이를 합산한다.
- 합산하고나서 도시 피자 배달 거리인 res와 비교한다. 그 합산값이 더 작다면 도시 피자 배달 거리를 합산값으로 릴리즈한다.
