백준 15686번 - 치킨 배달(C++)

- 삼성 SW 역량 테스트 기출문제

- 골드V

 

 처음엔 또 그래프? 라고 생각한 문제. 그러나 그래프 문제가 아니다. 

가장 먼저 생각한 풀이는 

1. BFS로 집과 치킨집의 거리를 넣어둠

2. DFS조합

3. 최소값 출력

 

그러나 BFS시에는 이쁘게 테이블 형태로 떨어지지 않는다. 너무 어렵게 생각했다. 그냥 각 좌표 받고 거리 구해서 순서대로 벡터에 넣어두면 된다.

문제의 핵심은 "조합" 이다.  즉 모든 경우의 수를 따져야하는 완전탐색 문제이다.

조합은 DFS로 구현하는 것이 가장 일반적이다. 예전에 공부해뒀는데 또 까먹어서 다시공부했다. 어휴

 

#include <iostream>
#include <queue>
#include <cmath>
#define MAX 51
#define INT_MAX 10000000
using namespace std;
int N, M;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
int boad[MAX][MAX];

vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
vector<int> chickendistance[100];
int C = 0;
int H = 0;
int answer = INT_MAX;
bool check[15] = { false, };

void BruteForce() {
	int dis = 0;
	for (int i = 0; i < H; i++) {
		int mini = INT_MAX;
		for (int j = 0; j < chickendistance[i].size(); j++)
			if (check[j] == true) {
				if (mini > chickendistance[i][j]) {
					mini = chickendistance[i][j];
				}
			}
		dis += mini;
	}
	if (answer > dis)
		answer = dis;
}

void combination(int num, int index, int cnt) {
	if (cnt == num) {
		BruteForce();
		return;
	}
	for (int i = index; i < C; i++) {
		if (check[i] == true)
			continue;
		check[i] = true;
		combination(num, i, cnt + 1);
		check[i] = false;
	}
}



int main() {
	ios_base::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 >> boad[i][j];
			if (boad[i][j] == 1) { // 집
				house.push_back(make_pair(i, j));
				H++;
			}
			else if (boad[i][j] == 2) {
				chicken.push_back(make_pair(i, j));
				C++;
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < C; j++) {
			int tmp = abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second);
			chickendistance[i].push_back(tmp);
		}
	}
	for (int i = 1; i <= M; i++) {
		combination(i, 0, 0);
	}

	cout << answer;
}

 처음에 선언 잘 못해서 에러났다. 저런 에러는 처음봐서 정리 해둘 예정