[코드트리] 병원 거리 최소화하기

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/min-of-hospital-distance/description?page=1&pageSize=20

💻 문제 풀이 : C++

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

#define MAP_SIZE 55

using namespace std;

struct Coord
{
	int row;
	int col;
};

int n, m;
int MAP[MAP_SIZE][MAP_SIZE];
int used[MAP_SIZE];
int minAns;

int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };

vector<Coord> client;
vector<Coord> hospital;
vector<Coord> picked;

int getAbs(int a)
{
	return a > 0 ? a : (-1) * a;
}

int getDist(Coord a, Coord b)
{
	return getAbs(a.row - b.row) + getAbs(a.col - b.col);
}

void CLEAR()
{
	n = 0;
	m = 0;
	minAns = 213456890;
	memset(MAP, 0, sizeof(MAP));
	client.clear();
	hospital.clear();
	picked.clear();
}

void INPUT()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> MAP[i][j];
			if (MAP[i][j] == 1)
				client.push_back({ i, j });
			else if (MAP[i][j] == 2)
				hospital.push_back({ i, j });
		}
	}
}

int simulation()
{
	int sumDist = 0;

	for (int i = 0; i < client.size(); i++)
	{
		int tmp = 2134567890;
		for (int j = 0; j < m; j++)
		{
			tmp = min(tmp, getDist(client[i], picked[j]));
		}
		sumDist += tmp;
	}

	return sumDist;
}

void dfs(int depth, int start)
{
	if (depth >= m)
	{
		minAns = min(minAns, simulation());
		return;
	}
	for (int i = start; i < hospital.size(); i++)
	{
		if (used[i] == 1) continue;
		used[i] = 1;
		picked.push_back(hospital[i]);
		dfs(depth + 1, i+1);
		picked.pop_back();
		used[i] = 0;
	}
}

void SOLVE()
{
	dfs(0, 0);

	cout << minAns << "\n";
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	return 0;
}

📌 memo 😊

순열 vs 조합 구분하기

해당 문제는 순열로 할 경우 시간초과 발생!!
=> 조합으로 병원을 선택해야 함

최단거리 구하기

최단거리 구하는 공식이 주어졌으므로, BFS가 아니라 공식을 이용하여 계산해야 함!!