[백준] 치킨배달 | 삼성

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

 

분류:: BruteForce, DFS

 

1. 문제 이해 및 해결과정

1. 치킨 집의 총 개수를 K 라고 하면 그 중 M개를 고름 => 조합 순서없음,중복없음 2. M개에서 치킨거리를 구하고, 치킨거리 중 최소 값을 누적해서 도시의 치킨거리를 구함 [python] 1. 치킨집의 개수가 더 작으니까 치킨집을 기준으로 2. 치킨집의 위치와 집의 위치 각각 저장한다 3. 치킨집을 m개 만큼 뽑는다. 4. 뽑힌 치킨 집부터 집까지 모든 거리를 계산하여 저장한다 5. 치킨 집부터 집까지의 치킨거리가 이전 치킨거리보다 작은경우 작은 것을 저장한다.   ex)   dist는 (0,2) , (1,4), (2,1), (3,2) 인 집에서 치킨집까지의 최소거리를 저장한다.   dist = [1,2,2,2] => [1,2,1,1] 6. dist의 합이 최소인 경우가 답이 된다

- 조합을 구하는 부분이 어려웠다. 

 

출처 : na982 유튜브 참고

 

2. 풀이방법

1. [C++]

#if 01
//치킨배달
//https://www.acmicpc.net/problem/15686
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 50
using namespace std;

int map[MAX][MAX];
int N, M;
int sol = 0x7fffffff;

struct pos {
	int h;
	int w;
};
vector<pos> home, chicken,selected;


void DFS(int idx,int cnt ) { //조합 재귀 

	//if (n > chicken.size())return; //종료조건 : 치킨집 개수보다 클 때
	if (cnt ==	M) { 
		int sum=0;

		for (int i = 0; i < (int)home.size(); i++) {
			int d = 99999999;
		
			for (int j = 0; j < (int)selected.size(); j++) {
			//for (auto j : selected) {
				d = min(d, abs(home[i].h - selected[j].h) + abs(home[i].w - selected[j].w));
			}
			sum += d;

		}
		sol = min(sol, sum);
		return;
	}

	for (int i = idx; i < (int)chicken.size(); i++) {
		//치킨집 선택 후 
		selected.push_back(chicken[i]);
		DFS(i + 1, cnt + 1);
		selected.pop_back();
	}


}
void InputData() {
	
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int tmp;
			scanf("%d", &tmp);
			if (tmp == 1) home.push_back({ i,j }); //집
			else if (tmp == 2) chicken.push_back({ i,j }); //치킨
		}
	}


}
int main() {

	freopen("input.txt", "r", stdin);

	InputData();
	DFS(0,0);
	printf("%d", sol);

}
#endif

 

2. [python]

#치킨배달
#https://www.acmicpc.net/problem/15686
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
home=[]
chicken=[] #치킨집
result=[]
for i in range(n):
    for j in range(n):
        if board[i][j]==1:#집
            home.append((i,j))
        if board[i][j]==2: #치킨집
            chicken.append((i,j))
check=[0]*(len(chicken)) #치킨집 체크 배열
selected=[] #선택된 치킨집의 개수
def chicken_distance(chick):
    dist = [5000] * (len(home))
    for i,j in chick:
        for k in range(len(home)):
            a,b=home[k]
            tmp=abs(i-a)+abs(j-b)
            dist[k]=min(dist[k],tmp)
    return sum(dist)

#치킨집 중에서 m개 만큼 뽑음
def dfs(d,s):
    res=0
    if d==m:
        for i in range(len(chicken)):
            if check[i]==1:
                selected.append(chicken[i])
        #print(selected)
        cd=chicken_distance(selected)
        res=max(cd,res)
        selected.clear()
        #print(res)
        result.append(res)
    else:
        for i in range(s,len(chicken)):
            check[i]=1
            dfs(d+1,i+1)
            check[i]=0


dfs(0,0)
print(min(result))

3. [python] 조합 라이브러리 사용

#치킨배달
#https://www.acmicpc.net/problem/15686
import sys
from itertools import combinations
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
home=[]
chicken=[] #치킨집
result=[]
for i in range(n):
    board=list(map(int,input().split()))
    for j in range(n):
        if board[j]==1:#집
            home.append((i,j))
        if board[j]==2: #치킨집
            chicken.append((i,j))

selected=list(combinations(chicken,m)) #선택된 치킨집 조합

def chicken_distance(selected):
    res=0
    for a,b in home:
        tmp=1e9
        for i, j in selected:
            tmp=min(abs(i-a)+abs(j-b),tmp)
        res+=tmp
    return res

res=1e9
for sel in selected:
    res=min(res,chicken_distance(sel))

print(res)

 

3. 오답원인

 

-  d = min(d, abs(home[i].h - selected[j].h) + abs(home[i].w - selected[j].w));

  :selected를 chicken으로 해놓고 틀린것을 발견못해 4시간은 소비한 것 같다..ㅠ

 

-범위기반 for문

 : vector <int> 로 받을때는 for(auto j: selected) 가 되지만 vector <pos>로 받을 때는 되지 않는다.

 

 

 

4. 알게된 점