[C++] 피자 배달 거리(DFS) 🔥

📄문제

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다. 

행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.
집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다.

예를 들어, 도시의 지도가 아래와 같다면

 

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.
최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.

시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.
도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

 

⬇️ 입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.
둘째 줄부터 도시 정보가 입력된다.

4 4 0 1 2 0 1 0 2 1 0 2 1 2 2 0 1 2

 

⬆️ 출력

첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

6

 

📝 풀이

#include <iostream>
#include <vector>
using namespace std;

int N, M, minRes = INT_MAX;
vector<pair<int, int>> home;
vector<pair<int, int>> pizza;

int select[12];

void DFS(int l, int s)
{
	// 피자집 M개를 다 뽑았다면?
	if (l == M)
	{
		// 도시 거리
		int cityDistance = 0;

		// 모든 집을 계산
		for (int i = 0; i < home.size(); ++i)
		{
			int pizzaDistance = INT_MAX;

			for (int j = 0; j < M; ++j)
			{
				// 피자집으로부터 거리를 구하기
				int dist = abs(home[i].first - pizza[select[j]].first) + abs(home[i].second - pizza[select[j]].second);

				// 피자집과 집의 최소 거리를 갱신
				pizzaDistance = min(pizzaDistance, dist);
			}

			// 도시 거리 더하기
			cityDistance += pizzaDistance;
		}

		// 도시 최소 거리 구하기
		minRes = min(minRes, cityDistance);
	}
	else
	{
		// pizza 중에서 M개를 뽑기 (DFS로 M개를 뽑기)
		for (int i = s; i < pizza.size(); ++i)
		{
			select[l] = i;
			DFS(l + 1, i + 1);
		}
	}
}

int main()
{
	scanf_s("%d %d", &N, &M);

	int input;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			scanf_s("%d", &input);

			if (input == 1)
				home.push_back({ i, j });
			else if (input == 2)
				pizza.push_back({ i, j });
		}
	}

	DFS(0, 0);

	printf("%d", minRes);
}

• DFS로 N개 중 M개를 뽑아 계산하는 방법으로 해결하였습니다.
• 각 피자집으로부터 집 까지의 최소 거리를 계산한 후 도시 거리를 구하여 최소 도시 거리를 구합니다.