[c++] 백준 - 치킨 배달 (15686번)

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

DFS의 응용문제로 보이고, vector와 구조체를 활용하면 간단하게 연산이 가능하다.

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

int N, M;
int map[51][51];
int minLength = 100000000;

typedef struct {
	int x;
	int y;
	int len;
}house;

vector <house> h;

typedef struct{
	int x;
	int y;
	bool select;
}chicken;

vector <chicken> c;

void setLength() {
	for (int k = 0; k < h.size(); k++) {
		int min = 100000000;
		
		for (int i = 0; i < c.size(); i++) {
			if (c[i].select == true)
			{
				int tmp = abs(c[i].x - h[k].x) + abs(c[i].y - h[k].y);
				if (tmp < min)
					min = tmp;
			}
		}
		h[k].len = min;
	}
}
int getLength() {
	int tmp = 0;
	for (int i = 0; i < h.size(); i++)
		tmp += h[i].len;
	return tmp;
}

void DFS(int idx, int cnt) {
	
	if (cnt == M) {
		setLength();
		int tmp = getLength();
		if (tmp < minLength)
			minLength = tmp;
		return;
	}
	for (int i = idx; i < c.size(); i++) 
	{
		if (c[i].select == true) continue;
		c[i].select = true;

		DFS(i, cnt + 1);
		c[i].select = false;
	}
}

int main() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				house tmp;
				tmp.x = i;
				tmp.y = j;
				tmp.len = 0;
				h.push_back(tmp);
			}
			if (map[i][j] == 2) {
				chicken tmp;
				tmp.x = i;
				tmp.y = j;
				c.push_back(tmp);
			}
		}
	DFS(0, 0);
	cout << minLength;
}