[백준][완전 탐색] 15686 치킨 배달 c++구현

목차

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

문제

나름 쉬운 문제였는데 구상을 안하고 해서 오래 걸렸다..

 

 

문제 구현 방향

문제의 범위를 보면 충분히 무식하게 탐색할 수 있는 범위이다.

따라서 모든 조합을 구해 모두 탐색해 보면 구할 수 있는 문제이다.

 

 

구현 시 참고

https://be-senior-developer.tistory.com/49

[알고리즘] 순열과 조합 c++ 구현

 

코드 구현

#include <iostream>
#include<vector>
#include<math.h>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;

vector<int> ans;  //치킨거리 저장해 놓을 곳
vector<pair<int, int>> house;  //폐업할 치킨 집
vector<pair<int, int>> m;   //조합을 저장할 곳

int original[100][100] = { 0 };
int board[100][100] = { 0 };
int N, M;

void reset() {  //초기화 해주는 함수
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			board[i][j] = original[i][j];
		}
	}
}

void close(vector <pair<int, int>>& v) {  // 치킨집 폐업 함수
	for (auto p: v)
		board[p.second][p.first] = 0;
}

int search(int x, int y) {  //탐색해서 가장 작은 값 반환
	int min = 50000;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 2) {
				int diameter = abs(i - y) + abs(j - x);  
				if (min > diameter)
					min = diameter;
			}
		}
	}
	return min;
}

void combi(int idx, vector <pair<int, int>> v) {  
	if (v.size() == house.size() -  M) {  //폐업하고 남은수에 다다를 경우
		reset();
		close(v);
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] == 1) 
					sum += search(j, i);
			}
		}
		ans.push_back(sum);
		return;
	}
	for (int i = idx; i < house.size(); i++) {
		v.push_back({ house[i].first, house[i].second });
		combi(i + 1, v);
		v.pop_back();
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> original[i][j];
			if (original[i][j] == 2)  //원본 배열 따로 저장
				house.push_back({ j, i });  //치킨집 좌표 미리 저장
		}
	}
	combi(0, m);
	cout << *min_element(ans.begin(), ans.end());   //가장 작은 값 반환
}