백준 15686 C++ - 치킨배달

Intro

문제해결 및 소스코드

NxN 크기의 Map에 빈칸(0), 집(1), 치킨집(2)의 정보가 주어진다.

구하고자하는것은 모든 치킨집들 중 M개를 선택한 뒤, 모든 각 집에 대해서 최소 치킨거리를 구하여 더해주는것이다.

따라서 다음과 같은 작업이 필요하다.

• 모든 치킨집들 중 M개를 선택하는 방법
  • 치킨집의 순서는 상관없다 -> (A,B)를 선택하는것과 (B,A)를 선택하는것은 같은 결과.
  • 치킨집을 중복 선택할수없다 -> (A,A)와 같이 같은 치킨집을 여러번 선택 불가.
  • 따라서 “조합” 을 이용한다.
• 각 집에 대해서 최소 치킨거리 구하기
  • 집 위치만을 저장할 변수가 필요.

  • 해당 집 기준으로 선택된 M개의 치킨집에 대해 거리 계산. ex. 집(1,2) 치킨집(4,3) ->

    1-4

    +

    2-3

    = 4

  • 최소 치킨거리만 기억하여 최종 치킨거리 도출

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int N, M, ans = INT_MAX;
int map[50][50];
bool selected[13];		// 중복검사용 (치킨집은 최대 13개)

vector<pair<int, int>> house, chicken, temp;

int Distance()
{
	int sum = 0;

	// 각 집에 대해서
	for (int i = 0;i < house.size();i++)
	{
		int houseX = house[i].first;		// 집의 x좌표
		int houseY = house[i].second;		// 집의 y좌표
		int dist = INT_MAX;					// 임의 치킨거리

		// 선택된 치킨집들에 대해서
		for (int j = 0;j < temp.size();j++)
		{
			int chickenX = temp[j].first;	// 치킨집 x좌표
			int chickenY = temp[j].second;  // 치킨집 y좌표
			int d = abs(houseX - chickenX) + abs(houseY - chickenY);	// 치킨거리계산

			// 최소 치킨거리
			dist = min(dist, d);
		}
		// 최소 치킨거리의 합
		sum += dist;
	}
	return sum;
}

// M개의 치킨집 고르기(조합)
void Select_Chicken(int depth, int cnt)
{
	// M개를 모두 골랐을 때
	if (cnt == M)
	{
		ans = min(ans, Distance());
		return;
	}

	for (int i = depth;i < chicken.size();i++)
	{
		// 이미 고른 치킨집일 경우
		if (selected[i] == true) continue;
		selected[i] = true;

		// 고른 치킨집은 temp에 저장
		temp.push_back(chicken[i]);

		// 다음 치킨집 고르기
		Select_Chicken(i + 1, cnt + 1);
		selected[i] = false;

		// 선택 취소
		temp.pop_back();
	}
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	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) house.push_back(make_pair(i, j));
			// 치킨집 위치 저장
			if (map[i][j] == 2) chicken.push_back(make_pair(i, j));
		}
	}

	Select_Chicken(0, 0);
	cout << ans;

	return 0;
}