[백준] 15686번 치킨 배달

문제: 15686번: 치킨 배달

basic-algo-lecture/workbook/0x0D.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0D.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>
#include <sstream>
#include <tuple>

using namespace std;

vector<vector<int>> city;
vector<pair<int, int>> chickens; // 치킨집 위치
vector<pair<int, int>> persons; // 사람집 위치
int minDist = INT_MAX;
int n, m; // 도시의 크기는 n*n, m개의 치킨집만 살리기
vector<int> personChickDist; // 사람의 치킨거리
vector<int> visitChicken; // 치킨집 방문 횟수

void Funct(int functM, int prevIdx) {
	if (functM == m) {
		int tmpDist = 0;

		// 각 집의 치킨 거리 합하기
		for (int i = 0; i < personChickDist.size(); i++) {
			tmpDist += personChickDist[i];
		}

		// 거리 갱신
		if (tmpDist < minDist) {
			minDist = tmpDist;
		}

		return; // 빠져나가깅~~
	}

	// 아직 치킨집 다 안 골랐으면 다시 ㄱㄱ
	for (int i = prevIdx + 1; i < chickens.size(); i++) {
		if (visitChicken[i] == 1) continue; // 이미 방문한 치킨집이면 패스!

		vector<int> prevDist = personChickDist; // 이전 치킨 거리 저장

		pair<int, int> chickPos = chickens[i];
		for (int j = 0; j < persons.size(); j++) {
			pair<int, int> personPos = persons[j];

			// 치킨 거리 구하기
			int dist = abs(chickPos.first - personPos.first) + abs(chickPos.second - personPos.second);

			// 치킨 거리 갱신
			if (personChickDist[j] > dist) {
				personChickDist[j] = dist;
			}
		}
		visitChicken[i] = 1; // 방문 표시
		Funct(functM + 1, i); // 파고 들어강~~
		visitChicken[i] = 0; // 방문 표시 제거
		personChickDist = prevDist; // 원래 값으로 복원
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	city = vector<vector<int>>(n);
	for (int i = 0; i < n; i++) {
		city[i] = vector<int>(n);

		for (int j = 0; j < n; j++) {
			cin >> city[i][j]; // 입력받기

			if (city[i][j] == 1) {
				// 사람집
				persons.push_back(make_pair(i, j));
			}
			else if (city[i][j] == 2) {
				// 치킨집
				chickens.push_back(make_pair(i, j));
			}
		}
	}
	personChickDist = vector<int>(persons.size(), INT_MAX); // 각 사람의 치킨 거리
	visitChicken = vector<int>(chickens.size()); // 각 치킨집 방문 여부

	Funct(0, -1);
	cout << minDist;


	return 0;
}

 

보자마자 백트래킹 이용해야 하는 문제라는 생각이 들었다. 각 사람마다 치킨 거리를 백트래킹을 이용해서 어떻게 갱신할 수 있을까 고민했다. 떠오른 방법은 각 사람의 치킨 거리를 저장할 벡터를 하나 선언해놓는다. 그래서 백트래킹으로 파고 들어가면서 새로운 치킨집을 만날 때마다 치킨 거리를 갱신해준다. 

 

만약 M 개의 치킨집을 다 골랐다면 현재까지의 각 사람의 치킨거리를 다 더해주고, 이게 이전 값보다 더 작다면 갱신해주도록 했다.

 

처음에 실수한 부분은 Funct 에서 return 을 만나 이전으로 돌아왔을 때 각 사람의 치킨 거리를 Funct 로 들어가기 전 값으로 다시 복원해줘야 하는 걸 놓친것이다. 원래 값으로 복원해주지 않으면 이상한 값이 되어버린다.. 백트래킹 문제 풀 때마다 조심해야 하는데 -_-;;