https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
1. 각 집과 치킨집과의 거리를 계산한다. 아래 케이스의 경우 집이 6개 치킨집이 5개이므로 30개의 값을 계산한다.
2. 백트래킹 알고리즘을 통해서 치킨집 개수 중에서 m개를 고른다. 이때 1,2,5번을 고르나 2,1,5번을 고르나 똑같기 때문에
오름차순으로 인덱스를 골라서 arr에 넣어준다.
3. 치킨집을 정했으면 각 집마다 정해진 치킨집과의 최소의 거리를 구하고 그 거리들을 다 더해준다.
4.위의 거리들의 최솟값을 구해서 도시의 치킨거리를 구해준다.
*i=index로 잘했는데 백트래킹 함수를 부를때 index+1로 해가지고 시간초과가 났다.
코드 꼼꼼히 보기!
#include<iostream>
#include<cmath>
using namespace std;
int city[52][52];// 0은 빈 칸, 1은 집, 2는 치킨집
int n, m;
int dtc[102][15];
int temp,ans=2000000000,mCnt,hCnt;
int arr[15];
bool visit[15];
int minD=100000;
void backtracking(int depth, int index)
{
if (depth == m+1)
{
/*cout << "arr" << endl;
for (int i = 0; i < 14; i++)
cout << arr[i] << " ";
cout << endl;*/
temp = 0;
for (int i = 1; i <= hCnt; i++)
{
minD = 1000000;
for (int j = 1; j <= m; j++)
{
if (dtc[i][arr[j]] < minD)
{
minD = dtc[i][arr[j]];
//cout << i << " :"<< arr[j] <<" "<< minD << endl;
}
}
temp += minD;
}
if (temp < ans)
ans = temp;
return ;
}
for (int i = index; i <= mCnt; i++)
{
if (!visit[i])
{
visit[i] = true;
arr[depth] = i;
backtracking(depth + 1, i+ 1);//index+1로 했음 ㅠ
visit[i] = false;
}
}
}
void calculationD(int y,int x, int idx)
{
int temp=0;
int mIdx = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (city[i][j] == 2)
{
temp = abs(y - i) + abs(x - j);
dtc[idx][mIdx] = temp;
mIdx++;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> city[i][j];
if (city[i][j] == 2)
mCnt++;
if (city[i][j] == 1)
hCnt++;
}
int index = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (city[i][j] == 1)
{
calculationD(i, j, index);
index++;
}
}
//모든 치킨집과의 거리를 계산
/*cout << endl;
for (int i = 1; i <= hCnt; i++)
{
for (int j = 1; j <= mCnt; j++)
{
cout << dtc[i][j] << " ";
}
cout << endl;
}*/
//m개를 뽑았을때 도시의 치킨 거리 계산
backtracking(1,1);
cout << ans;
}