피자 배달 거리(삼성 SW역량평가, DFS) / c++ / 제한시간 없음

▣ 문제

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개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다

 

▣ 입력 예시

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

 

▣ 출력 예시

6

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
#define x first
#define y second
using namespace std;

int n, m, ans, mini = 2147000000;
vector<pair<int, int> > pizza;
vector<pair<int, int> > house;
int visit[20];

void dfs(int s, int level) {
	int i, j;
	int sum = 0;
	int temp;
	if (level == m) {
		for (j = 0; j < house.size(); j++) {
			int dis = 2147000000;
			for (int k = 0; k < m; k++) {
				temp = abs(house[j].x - pizza[visit[k]].x) + abs(house[j].y - pizza[visit[k]].y);
				if (temp < dis)dis = temp;
			}
			sum += dis;
		}
		if (sum < mini)mini = sum;
	}
	else {
		for (i = s; i < pizza.size(); i++) {
			visit[level] = i;
			dfs(i + 1, level + 1);
		}
	}
}

int main() {
	int i, j, a;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			scanf("%d", &a);
			if (a == 1)house.push_back(make_pair(i, j));
			else if (a == 2)pizza.push_back(make_pair(i, j));
		}
	}
	dfs(0,0);
	printf("%d\n", mini);
	return 0;
}

visit[ ]에 몇번째 피자집이 선택되었는지를 입력한다.

 

if(level==m)에서 각 선택한 피자집과 집의 좌표를 temp에 저장시키고 그 합은 sum에 저장한다.

 

제일 작은 sum 값을 mini에 저장시키고 마지막으로 출력한다.

 

.

 

문제를 풀때 조합을 염두해두고 풀어야하는 유형

 

백준에도 똑같은 문제가 있다. 참고하시길

www.acmicpc.net/problem/15686