C++ / 백준 / 15686 / 치킨 배달

문제

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

15686번: 치킨 배달

문제풀이

단순하게 풀면 메모리랑 시간 초과가 날까 봐 좋은 방법이 있나 생각했는데 떠오르는 게 없어 모든 경우를 탐색하게 했다.

N, M을 입력받고 0, 1, 2 값을 입력받으면서 1이면 벡터 home개수를 늘리고 y, x좌표를 넣어준다.

2이면 벡터 chicken개수를 늘리고 y, x좌표를 넣어준다.

모든 입력이 끝났으면 각 치킨집에서 모든 집에 대해 거리가 얼마인지 계산하여 dir벡터에 입력해준다.

abs를 이용하여 y좌표는 y좌표끼리, x좌표는 x좌표끼리 뺄셈을 하여 절댓값을 구한다.

벡터 min_dir을 집의 개수만큼 생성하고 값을 999999로 잡아준다. (최솟값을 구해야 하기 때문에 0이 아닌 안 넘을 거 같은 값을 넣어줌)

치킨집에 대해 DFS를 돌린다.

idx는 치킨집의 인덱스 값, cnt는 해당 치킨집을 포함시키면 +1을 한다.

 

cnt가 M값과 같다면 min_dir벡터를 탐색하여 방문하지 않은 집이 있는지 확인한다. 999999이면 방문을 하지 않은 것이다.

모든 집을 방문하여 모든 값이 바뀌었다면 거리를 모두 더해 sum값을 구하고 answer값과 비교하여 더 적은 수를  answer에 저장한다.

 

cnt가 M값보다 적으면 다음 치킨집이 있는지 확인을 한다.

있다면 두 가지 경우가 있다.

1. 이번 치킨집은 포함시키지 않은 상태로 DFS를 돌린다.

2. 이번 치킨집을 포함시키기 위해 현재 치킨집 기준으로 min_dir의 값보다 적다면 min_dir값을 경신한다.

모든  집을 돌았다면 DFS를 돌린다.

 

모든 DFS 실행이 끝났으면 answer을 출력한다.

 

코드

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

int N, M;
int home_size;
vector<vector<int>>dir;
int answer=999999;

void DFS(int idx, int cnt, vector<int>min_dir) {
	int idx2(0);
	if (cnt == M) {
		bool visit(true);
		int sum(0);
		for (idx2 = 0; idx2 < min_dir.size(); ++idx2) {
			if (min_dir[idx2] == 999999) {
				visit = false;
				break;
			}
			sum += min_dir[idx2];
		}
		if (visit)
			answer = min(answer, sum);		
	}
	else {
		if (idx + 1 <= dir.size()) {
			DFS(idx + 1, cnt, min_dir);
			for (idx2 = 0; idx2 < min_dir.size(); ++idx2)
				min_dir[idx2] = min(min_dir[idx2], dir[idx][idx2]);			
			DFS(idx + 1, cnt + 1, min_dir);
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;

	int y(0), x(0);
	int idx(0), idx2(0);
	int num(0);
	vector<pair<int ,int>>home;
	vector<pair<int ,int>>chicken;
	
	for (y = 0; y < N; ++y) {
		for (x = 0; x < N; ++x) {
			cin >> num;
			if (num == 1)
				home.push_back({ y,x });
			else if (num == 2)
				chicken.push_back({ y,x });
		}
	}
	dir = vector<vector<int>>(chicken.size(), vector<int>(home.size(), 0));
	
	for (idx = 0; idx < chicken.size(); ++idx) {
		for (idx2 = 0; idx2 < home.size(); ++idx2) {
			dir[idx][idx2] = abs(chicken[idx].first - home[idx2].first) +
				abs(chicken[idx].second - home[idx2].second);
		}
	}
	
	vector<int>min_dir(home.size(), 999999);

	DFS(0, 0, min_dir);

	cout << answer;
}