백준 Gold 5 치킨배달

치킨배달 (백준 Gold 5)

https://www.acmicpc.net/problem/15686

백트래킹 문제이지만
오랜만에 백트래킹을 접해서 그런것인지
아니면 이 문제가 약간의 응용이 필요해서 그런건지
시간 초과가 발생하였다

처음 시도한 Code

#include<iostream>
#include<vector>
#include<math.h>
#include<unordered_set>
#include<limits.h>

using namespace std;

struct pos
{
	pos(int y, int x)
	{
		this->y = y;
		this->x = x;
	}

	int y, x;
};

int ChickDis(const pos& a, const pos& b)
{
	return abs(a.y - b.y) + abs(a.x - b.x);
}


void recur(const vector<pos>& houses, const vector<pos>& chicks, vector<bool>& visited, unordered_set<int>& selected, int count, int m, int value, int& result)
{
	// 1을 기준으로 chicks 중 가장 값이 적은 녀석을 선택
	// 그 녀석이 visited에 이미 존재하는지

	// 더 돌 필요 없음
	if (value > result)
		return;

	int hs = houses.size();
	int cs = chicks.size();

	// 재귀 종료
	if (count == hs)
	{
		if (value < result)
			result = value;

		return;
	}

	if (selected.size() < m)
	{
		for (int i = 0; i < hs; i++)
		{
			if (visited[i])
				continue;

			visited[i] = true;

			int idx = 0;
			int bestMin = INT_MAX;
			bool bNew = false;

			for (int j = 0; j < cs; j++)
			{
				int val = ChickDis(houses[i], chicks[j]);
				if (val < bestMin)
				{
					idx = j;
					bestMin = val;
				}
			}

			if (selected.find(idx) == selected.end())
			{
				bNew = true;
				selected.insert(idx);
			}

			recur(houses, chicks, visited, selected, count + 1, m, value + bestMin, result);

			if (bNew)
			{
				selected.erase(idx);
			}

			visited[i] = false;
		}
	}
	else
	{
		// 이미 다 선택되어 있다면 그중에서 전부 골라야 함
		int tempSum = value;
		for (int i = 0; i < hs; i++)
		{
			if (visited[i])
				continue;

			int bestMin = INT_MAX;

			for (int v : selected)
			{
				int val = ChickDis(houses[i], chicks[v]);
				if (val < bestMin)
					bestMin = val;
			}

			tempSum += bestMin;
		}

		if (tempSum < result)
			result = tempSum;
	}

}


int main()
{
	int n, m;
	cin >> n >> m;

	vector<pos> houses, chicks;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int t;
			cin >> t;
			if (t == 1)
			{
				houses.emplace_back(pos(i, j));
			}
			else if (t == 2)
			{
				chicks.emplace_back(pos(i, j));
			}
		}
	}

	int result = INT_MAX;
	vector<bool> visited(houses.size() + 1, false);
	unordered_set<int> selected;

	recur(houses, chicks, visited, selected, 0, m, 0, result);

	cout << result;

	return 0;
}

이 코드는 기본적으로
맨해튼 거리를 함수로 따로 빼고
‘치킨집’과 ‘집’을 pos로 정리하여
‘집’을 선택하고 ‘치킨집’을 고르는 방식으로 진행하였다

다만 4번째 예제에서 시간초과가 발생하여
‘이미 m만큼 골랐다면’ 남은 값은 한번에 처리하는 방식으로 진행했다

결국 제출했을 땐, 시간초과가 발생하였고
최적화가 필요하다고 느꼈다

---

개선할 점

1. 어차피 치킨집에 대한 모든 선택을 고려해야 함
   그렇다면 먼저 치킨집을 m만큼 선택하면?
   -> 총 n개의 치킨집에서 m개의 치킨집을 고름
   (조합?)
   
2. 다 고른 이후, 각각의 집에서 가까운 치킨집을 골라
   그 최소 거리를 더한다
   
3. 그 최소 거리의 합들을 result와 비교하여
   최종적인 최소 치킨 거리를 구한다
   

최종 제출 코드

#include<iostream>
#include<vector>
#include<math.h>
#include<limits.h>

using namespace std;

struct pos
{
	pos(int y, int x)
	{
		this->y = y;
		this->x = x;
	}

	int y, x;
};

int ChickDis(const pos& a, const pos& b)
{
	return abs(a.y - b.y) + abs(a.x - b.x);
}

void Recur(const vector<pos>& houses, const vector<pos>& chicks, vector<int>& picked, int start, int m, int& result) 
{
	if (picked.size() == m) 
	{
		int total = 0;
		for (const auto& h : houses) 
		{
			int minDist = INT_MAX;
			for (int idx : picked) 
			{
				minDist = min(minDist, ChickDis(h, chicks[idx]));
			}
			total += minDist;
		}
		result = min(result, total);
		return;
	}

	// 치킨 집 m개 고르기
	for (int i = start; i < chicks.size(); i++) 
	{
		picked.push_back(i);
		Recur(houses, chicks, picked, i + 1, m, result);
		picked.pop_back();
	}
}

int main()
{
	int n, m;
	cin >> n >> m;

	vector<pos> houses, chicks;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int t;
			cin >> t;
			if (t == 1)
			{
				houses.emplace_back(pos(i, j));
			}
			else if (t == 2)
			{
				chicks.emplace_back(pos(i, j));
			}
		}
	}

	int result = INT_MAX;
	vector<int> selected;

	Recur(houses, chicks, selected, 0, m, result);

	cout << result;

	return 0;
}

정리

백트래킹은 모든 경우를 ‘탐색’하는
브루트 포스의 일환이지만
그 탐색지가 목표에 적합하지 않으면
‘한 단계’를 ‘돌아가’ 다른 선택지를 시도하는 것

그렇기에 재귀를 통해 구현하는 편

다만 이번 문제는 엄밀히 따지자면
‘조합’과 ‘재귀’를 사용하여 문제를 해결하였고
중간 합을 쳐내는 과정을 추가해야 백트래킹이라 말할 수 있을것이다

• 조합 : n개 중 m개 선택 (치킨집 선택에 사용)
  
• 재귀 : m개의 요소를 선택하는 반복 과정에 사용
  
• 백트래킹 : 만약 중간 합이 쓸데없이 크다면 return하여 가지치기 했다면 설명 가능
  

백트래킹 적용한다면?

void Recur(const vector<pos>& houses, const vector<pos>& chicks, vector<int>& picked, int start, int m,int nowSum, int& result)  
{
    if (picked.size() == m) 
    {
        minSum = min(minSum, nowSum);
        return;
    }

    // 조건 불만족
    if (nowSum >= minSum) 
        return; 

    // 치킨 집 m개 고르기
	for (int i = start; i < chicks.size(); i++) 
	{
		picked.push_back(i);

        // 치킨 거리 구하기
        int nowBest = ...;

		Recur(houses, chicks, picked, i + 1, m,nowSum + nowBest,result);
		picked.pop_back();
	}
}