🙇‍♀️피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)

N×N 크기의 도시지도가 있습니다.

도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.

각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다.

각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다.

행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.

도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.

집과 피자집의 피자배달거리는 x1-x2 + y1-y2 이다.

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

0 1 0 0
0 0 2 1
0 0 1 0
1 2 0 2

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 1-2 + 2-3 = 2가 된다.

최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.

도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.

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

도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

▣ 입력설명
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.

둘째 줄부터 도시 정보가 입력된다.

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

▣ 입력예제 1 
4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2

▣ 출력예제 1
6

🚀풀이

백준의 치킨 배달 문제와 동일한 문제이다.

그 때 코드는 다음과 같다.

int cal = 0;
void pick(int num, vector<int>& picked, int toPick)
{
	if (toPick == 0)
	{
		// 치킨 집 선택하기
		for (int i = 0; i < picked.size(); ++i)
		{
			board[chick[picked[i]].first][chick[picked[i]].second] = 3;
		}

		// 치킨 거리 구하기
		cal = 0;
		for (int i = 0; i < house.size(); ++i)
		{
			pair<int, int> h = { house[i].first, house[i].second };

			int temp = 12345678;
			for (int y = 1; y <= n; ++y)
			{
				for (int x = 1; x <= n; ++x)
				{
					if (board[y][x] == 3)
					{
						temp = min(temp, abs(h.first - y) + abs(h.second - x));
					}
				}
			}
			cal += temp;
		}

		res = min(res, cal);

		// 치킨 집 원상복구
		for (int i = 0; i < picked.size(); ++i)
		{
			board[chick[picked[i]].first][chick[picked[i]].second] = 2;
		}

		return;
	}

	int smallest = picked.empty() ? 0 : picked.back() + 1;

	for (int next = smallest; next < num; ++next)
	{
		picked.push_back(next);
		pick(num, picked, toPick - 1);
		picked.pop_back();
	}
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

// 빈 칸 : 0
// 집 : 1
// 치킨집 : 2

int n, m, res = 123456789, houseCnt, chickCnt;
vector<vector<int>> board;
vector<pair<int, int>> chick;
vector<pair<int, int>> house;

void setting()
{
	cin >> n >> m;
	board = vector<vector<int>>(n + 2, vector<int>(n + 2));

	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			cin >> board[y][x];
			if (board[y][x] == 1)
				house.push_back({ y, x });
			if (board[y][x] == 2)
				chick.push_back({ y, x });
		}
	}

	houseCnt = house.size();
	chickCnt = chick.size();
}

int cal = 0;
void pick(int num, vector<int>& picked, int toPick)
{
	if (toPick == 0)
	{
		// 치킨 집 선택하기
		for (int i = 0; i < picked.size(); ++i)
		{
			board[chick[picked[i]].first][chick[picked[i]].second] = 3;
		}

		// 치킨 거리 구하기
		cal = 0;
		for (int i = 0; i < house.size(); ++i)
		{
			pair<int, int> h = { house[i].first, house[i].second };

			int temp = 12345678;
			for (int y = 1; y <= n; ++y)
			{
				for (int x = 1; x <= n; ++x)
				{
					if (board[y][x] == 3)
					{
						temp = min(temp, abs(h.first - y) + abs(h.second - x));
					}
				}
			}
			cal += temp;
		}

		res = min(res, cal);

		// 치킨 집 원상복구
		for (int i = 0; i < picked.size(); ++i)
		{
			board[chick[picked[i]].first][chick[picked[i]].second] = 2;
		}

		return;
	}

	int smallest = picked.empty() ? 0 : picked.back() + 1;

	for (int next = smallest; next < num; ++next)
	{
		picked.push_back(next);
		pick(num, picked, toPick - 1);
		picked.pop_back();
	}
}

void solve()
{
	// 치킨 집 m개만 남기고 다 없앤다
	// 치킨 거리를 구한다
	// 모든 경우를 탐색한다

	vector<int> test;
	pick(chickCnt, test, m);

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}

참고