문제 : https://www.acmicpc.net/problem/15686
깨달은 것
- 수학을 사용할 것 - 여기선 조합
- BackTracking을 처음 해봄
1. 수학을 사용할 것
처음에 이 문제를 봤을 때 특정 M개의 치킨 가게를 뽑아야한다는 것이 어려웠다. 그리고 또한 경우의 수를 봤을 때는 조합을 사용해서 경우의 수들을 구하는게 맞아 보였지만 시간초과가 뜰거 같아서 내키지 않았다.
설령 집(1)을 기준으로 주변 가까운 치킨집(2)를 DFS나 BFS를 통해 찾는다 하더라도 개수 M을 고려하면서 제일 치킨거리가 낮은 경우를 찾기가 어려웠다. 사실은 너무 어려워보였다 그래서 알고리즘 분류를 보니 브루트 포스와 백트래킹이 써있었다.
하지만, 문제는 언제 백트래킹을 쓰고, 언제 브루트 포스를 쓰는지 감이 안 왔다.
2. BackTracking을 처음 써봄
BackTracking이란 말 그대로 유망하지 않는 경우는 한정조건에 부합하지 않으므로 고려하지 않는다는 것이다. 이는 주로 DFS나 BFS에서 많이 쓰이는데 완전 탐색을 기반으로 탐색을 하다가 "한정조건"에 부합하지 않으면 그 전 단계로 다시 이동한다는 것이다.
이 문제에서는 백트래킹이 조합을 계산하는데 사용되었다.
예를 들어, a b c d e라는 리스트가 있다고 하자. 여기서 3개를 고르는 방법은, 총 5C3 = 10이다.
이를 그래프로 나타내면
사실은 d와 e도 근노드일 때를 그려야 하지만, 개수가 3개가 안되는 것이 자명하므로 그리지 않았다. a,b,c의 경우도 보면 3개가 되지 않은 가지들도 있다. 이렇게 3개가 되지 않는 경우들은 고려하지 않고 3개가 되는 경우들만 고려하도록 조합 계산을 짜야한다. 코드는 이렇다.
void combination(int start, int cnt)
{
if (cnt == M)
{
// start brute force search for minimum
cal_distance();
return;
}
for (int i = start; i < chicken.size(); i++)
{
tmp.push_back(chicken[i]);
cnt++;
combination(i + 1, cnt);
tmp.pop_back();
cnt--;
}
}if(cnt == M)인 부분에서 M개까지 세지 않도록 막아준다. 또한 재귀를 통해 M개 탐색이 다 끝난 후에는 cnt와 마지막 요소를 빼주는 것 또한 잊지 않아야한다.
브루트 포스는 마지막에 각 tmp마다 최소의 치킨거리를 구하여 모든 tmp의 경우들을 계산해서 비교해보는 것에서 사용하는 것이었다.
void cal_distance()
{
int total = 0;
for (int i = 0; i < home.size(); i++)
{
int m = 987654321;
for (int j = 0; j < tmp.size(); j++)
{
int new_dis = abs(home[i].first - tmp[j].first) + abs(home[i].second - tmp[j].second);
m = m > new_dis ? new_dis : m;
}
total += m;
}
if (total < res)
res = total;
}처음부터 너무 어렵게 생각했던 것 같다. 아직은 많이 부족하지만, 여러 알고리즘에 노출을 해보도록하고 언제 어떤 것을 사용할지 생각해보자.
