[구현&시뮬레이션] 백준 15686 치킨배달

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

15686번: 치킨 배달

수행시간 : 1시간 40분 / 난이도 : 골드 5

 

처음 문제를 읽고, 어? 할만한데? 하다가 그대로 1시간이 지나가버린 문제였다...

일반 완탐 + 구현 형식이 아니다. 만약 하나를 골라서 탐색을 했는데 그 값이 다음 값보다 좋은 값이 아니라면? 다시 돌아가서 복구해주고 다음 것을 탐색하는, 즉 백트래킹 자료구조가 필요했다.

요즘은 로직을 짜는 것에 시간을 더 투자하려고하는데, 전에 풀어봤던 비슷한 문제를 보니 로직을 건너뛰고 바로 코딩을 시작한 것이 문제였던것 같다. 백트래킹 함수만 잘 설정하면 나머지는 일반 구현이므로 쉽게 풀 수 있었다.

 

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

int n, m;
vector<vector<int>> v_map;
vector<pair<int, int>> chic;
vector<pair<int, int>> house;
int min_dis = 99999999;
int min_val = 99999999;

void input() {
	cin >> n >> m;
	v_map.resize(n, vector<int>(n));
	for (int i = 0; i < n;++i) {
		for (int j = 0;j < n;++j) {
			cin >> v_map[i][j];
			if (v_map[i][j] == 2) {
				chic.push_back({ i, j });
			}
			if (v_map[i][j] == 1) {
				house.push_back({ i,j });
			}
		}
	}
}
int check() {
	int size1 = house.size();
	int size2 = chic.size();
	int dis = 0;
	int ans = 0;
	for (int i = 0; i < size1;++i) {
		int temp_dis = 99999;
		int x = house[i].first;
		int y = house[i].second;
		for (int j = 0;j < size2;++j) {
			int nx = chic[j].first;
			int ny = chic[j].second;
			dis = abs(x - nx) + abs(y - ny);
			if (temp_dis > dis) {
				temp_dis = dis;
			}
		}
		ans += temp_dis; //ans 는 도시의 치킨거리
		//cout << ans << "\n";
	}
	return ans;
}

void sol(int cnt) {
	if (cnt == m) { //만약 cnt가 m개 뽑히면 종료
		int temp = check();
		cout << "1";
		if (min_val > temp) {
			min_val = temp;
		}
		return;
	}
	int size = chic.size();
	for (int i = 0;i < size;++i) {
		int x = chic[i].first;
		int y = chic[i].second;
		chic.erase(chic.begin() + i);
		sol(cnt - 1);
		chic.push_back({ x,y });
	}
}

int main() {
	input();
	sol(chic.size());
	cout << min_val;
}