백준 15686, 2차원 좌표에 대한 조합을 활용한 완전탐색 문제

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

15686번: 치킨 배달

해당 문제는 주어진 치킨 집 좌표 중에서 M개를 골라 도시의 치킨 거리를 구한 다음 최소값을 구해야 한다.

이전에 배웠던 그래프 탐색 문제와는 달리 많은 경우에 대해 탐색하고 계산해야 한다. 따라서 이는 완전탐색 문제로

분류할 수 있다.

 

1. 먼저 완전탐색으로 풀 시 시간복잡도를 확인한다. 해당 문제에서 치킨 집의 최대 개수가 13개이므로 조합으로 나올 수 있는 최대 개수는 13C6 or 13C7이다. 여기에 각 집마다 치킨 거리를 구해야 하므로 집의 최대 개수인 100(2N)을 곱하여 시간복잡도를 계산한다.
2. 만약 시간복잡도가 오버될 경우, 다른 알고리즘을 찾아야 한다.

Key Point

1. 조합을 구하는데 있어서 2차원 좌표계에 대한 값을 배열의 인덱스와 매핑한다.
   • 예를 들어, 배열에 [{1,3},{2,5},{3,4}]가 있을 경우 각각의 값은 인덱스인 0, 1, 2와 매핑된다. 따라서 실제 조합을 통한 배열에 저장되는 값은 pair가 아닌 int 형이며, 배열에 저장된 인덱스를 통해 실제 2차원 좌표에 접근한다.
2. 이 문제도 주어진 맵을 활용하여 문제를 해결해야 한다. 하지만 맵이 나왔다고 해서 DFS처럼 dy, dx를 무조건 쓸 필요는 없다. 또한 해당 문제는 경로를 찾는 것이 아니기 때문에 더더욱 필요가 없다. 다만 모든 경로를 탐색해야 하는 완전탐색 문제일 경우에는 dy, dx를 활용해야 한다.

문제 코드

#include<bits/stdc++.h>
using namespace std; 

int N, M, arr[51][51];
int minDist = 987654321; // 도시의 치킨 거리 최소 값 (비교를 위한 초기 값) 

vector<pair<int, int>> home, chicken;
vector<vector<int>> chickenList;

void combi(int start, vector<int> v){
	if(v.size() == M) {
		chickenList.push_back(v);
		return ;
	}
	
	for(int i = start + 1; i < chicken.size(); i++){
		v.push_back(i);
		combi(i, v);
		v.pop_back();
	}
	
	return;
}

int main() {
	
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> arr[i][j];
			if(arr[i][j] == 1) home.push_back({i,j});
			if(arr[i][j] == 2) chicken.push_back({i,j});
		}
	}
	
	// 조합 뽑아서 chickenList에 저장하기
	vector<int> v;
	combi(-1, v);
	
	// 각 조합마다 도시의 치킨 거리 구하기 : chickenList에서 각각의 조합을 꺼낸다
	for(vector<int> cList : chickenList){
		// home에서 하나씩 꺼내서 계산
		int total = 0; // 특정 조합에 대한 도시의 치킨 거리를 저장하는 변수 
		for(pair<int, int> _home : home){
			int _min = 987654321;
			// 특정 집에 대해서 치킨 집마다 거리 구하기 : cList에 담겨 있는 치킨 집의 좌표를 하나씩 꺼내서 계산
			for(int c : cList){
				int distance = abs(_home.first - chicken[c].first) + abs(_home.second - chicken[c].second);
				_min = min(_min, distance); // 특정 치킨 조합에 대한 한 집의 치킨 거리(최소값) 
			}
			total += _min; // 각 집의 치킨 거리를 더해서 특정 조합에 대한 도시의 치킨 거리 계산 
		}
		minDist = min(minDist, total);
	}
	
	cout << minDist << "\n"; 
	
	return 0; 
}

• 순열에 대한 재귀함수의 경우, depth를 포함한 여러 매개변수가 필요하지만 조합에 대한 재귀함수는 시작지점과 조합을 저장할 배열에 대한 포인터만 있으면 된다.

코드에 대한 그림 설명

 

 

 

 

 

 

 

 

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의