[백준] 15686번 : 치킨 배달 [C/C++]

#문제

15686번: 치킨 배달

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

15686번: 치킨 배달

 

---

#접근방법

이 문제는 모든 경우의 수를 구하는 브루트포스 유형의 문제이다. 브루트포스 알고리즘은 모든 경우의 수를 구하는 알고리즘이다. 비슷한 알고리즘인 백트래킹이 있는데 백트래킹 알고리즘은 모든 경우의 수를 찾을 때, 필요없는 부분은 가지치기하면서 구하는 알고리즘이다.

반응형

---

#풀이

#include <stdio.h>

int house[105][2],hnum;
int chicken[15][2],cnum;
int select[15],snum;
int n,m;
int ans = 987654321;

int diff(int x1, int y1, int x2, int y2){
	int num = 0;
	
	if(x1<x2) num += x2-x1;
	else num += x1-x2;
	
	if(y1<y2) num += y2-y1;
	else num += y1-y2;
	
	return num;
}

int result(){
	int min,sum=0,p;
		
	for(int i=0;i<hnum;i++){
		min = 987654321;
		for(int j=0;j<m;j++){
			p = diff(house[i][0],house[i][1],chicken[select[j]][0],chicken[select[j]][1]);
			
			if(min>p) min = p;
		}
		sum += min;
	}
	
	return sum;
}

void chicken_select(int k){
	if(snum==m){
		int res = result();
		if(ans>res) ans = res;
		return;
	}
	
	for(int i=k;i<cnum;i++){
		select[snum++] = i;
		chicken_select(i+1);
		snum--;
	}
	
	return;
}

int main(){
	int x;
	
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			scanf("%d",&x);
			if(x==1){
				house[hnum][0] = i;
				house[hnum++][1] = j;
			}
			else if(x==2){
				chicken[cnum][0] = i;
				chicken[cnum++][1] = j;
			}
		}
	
	chicken_select(0);
	
	printf("%d",ans);
	
	return 0;
}

 

위에서 설명한 것과 같이 이 문제는 모든 경우의 수를 구하는 브루트포스 유형이다. 이런 문제들은 푸는 방법은 알지만, 구현력이 약해서 못푸는 경우가 빈번하다. 그럴때는 구현 문제를 많이 풀어서 구현력을 기르고 브루트포스 문제를 풀면 쉽게 풀 수 있다.

 

치킨집 중에 M개를 고르고 각각의 집에서 M개의 치킨집 중에 치킨 거리가 가장 짧은 것을 구해서 누적시켜주면 한 가지 경우의 수에서 도시의 치킨 거리를 구할 수 있다. 이 도시의 치킨 거리들 중에서 최소값을 구하면 정답이다.

 

먼저 n을 입력받고 n*n의 도시를 입력받는다. 우리가 도시의 정보중에서 필요한 부분은 집의 좌표, 치킨의 좌표이다.

 

코드를 알기쉽게 짜기 위해서 3가지 함수를 만들었다.

chicken_select는 치킨집 중에서 M개를 선택하여 select배열에 저장시켜주는 함수이고,

result는 M개의 치킨집을 고른 도시의 치킨 거리의 최소값을 구해주는 함수이고,

diff는 집과 치킨의 좌표를 넣으면 치킨거리를 구해주는 함수이다.

 

result함수로 구한 값들 중에서 최소값을 구해주면 정답이다.

---

#성능

---

#정리

해당 문제가 모든 경우의 수를 구하는 브루트포스 알고리즘을 사용해야 한다는 것,

 

이를 구현할 수 있는 구현력을 갖추고 있으면 쉽게 풀 수 있는 문제였다.