[백준 15686] 치킨배달 (C++/Python)

1. 조건

- 도시 각 칸 : 빈칸 - 0 / 치킨집 - 1 / 집 - 2

- 치킨거리 : 집이랑 가장 가까운 치킨집의 거리

- 도시의 치킨거리 : 모든 집의 치킨거리의 합

 

2. 입력

- n : 지도 크기

- m : 살아남은 치킨집

- 지도

3. 출력

- 도시의 치킨거리

 

4. 알고리즘

1) 폐업에서 살아남은 치킨집 m개를 고른다.

 - 치킨집이 1,2,3,4,5 가 있을 때 1,2,3이나 2,3,1이나 3,1,2나 똑같다 -> 조합임

2) 집이랑 치킨집 m개중에서 가장 가까운 치킨거리를 구한다.

3) 모든 집들에 대해 2)를 수행해 도시의 치킨거리를 구한다.

 

---

C++)

1. 백트래킹

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define MAX_NUM 52
using namespace std;

int n, m;
vector<pair<int, int>> chicken;	// 치킨집 위치
vector<pair<int, int>> house;	// 집위치

bool visited[15];			// 치킨집 방문 여부
int surviveChicken[15];		// 폐업 안 하고 살아남은 치킨집
int ans = 987654321;

void func(int cnt, int st) {
	// 폐업 안 할 치킨집 m개 골랐으면
	if (cnt == m) {
		int sum = 0;

		// 집과
		for (int i = 0; i < house.size(); i++) {
			int temp = 987654321;
			int r1 = house[i].first;
			int c1 = house[i].second;

			// 치킨집들 사이의 치킨거리를 구한다
			for (int j = 0; j < m; j++) {
				int r2 = chicken[surviveChicken[j]].first;
				int c2 = chicken[surviveChicken[j]].second;

				temp = min(temp, abs(r1 - r2) + abs(c1 - c2));
			}

			sum += temp;
		}

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

	// 폐업 안 할 치킨집 구하기
	for (int i = st; i < chicken.size(); i++) {
		if (!visited[i]) {
			surviveChicken[cnt] = i;
			visited[i] = true;
			func(cnt + 1, i + 1);
			visited[i] = false;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;

	int temp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;

			// 집
			if (temp == 1)
				house.push_back({ i,j });
			// 치킨집
			else if (temp == 2)
				chicken.push_back({ i,j });
		}
	}

	func(0, 0);

	cout << ans << "\n";

	return 0;
}

 

 

 

2. next_permutation

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define MAX_NUM 52
using namespace std;

int n, m;

vector<pair<int, int>> chicken;	// 치킨집 위치
vector<int> surviveChicken;		// 치킨집 조합 구해야함
vector<pair<int, int>> house;	// 집 위치

int func(vector<int>& survivor) {
	int sum = 0;

	// 집과
	for (int i = 0; i < house.size(); i++) {
		int r1 = house[i].first;
		int c1 = house[i].second;

		int temp = 987654321;

		// 살아남은 치킨집들 중에서 가장 가까운 치킨집과의 거리 구함
		for (auto pos : survivor) {
			int r2 = chicken[pos].first;
			int c2 = chicken[pos].second;

			temp = min(temp, abs(r1 - r2) + abs(c1 - c2));
		}

		sum += temp;
	}

	return sum;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;

	int temp;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;

			if (temp == 1)
				house.push_back({ i,j });
			else if (temp == 2) {
				  surviveChicken.push_back(chicken.size() < m ? 0 : 1);
				  chicken.push_back({ i,j });
			}
		}
	}


	int ans = 987654321;

	// 조합 구하기
	do {
		int sum = 0;
		vector<int> survivor;

		for (int i = 0; i < chicken.size(); i++) {
			if (surviveChicken[i] == 0)		// 선택된 치킨집 
				survivor.push_back(i);
		}	

		ans = min(ans, func(survivor));
	} while (next_permutation(surviveChicken.begin(), surviveChicken.end()));

	cout << ans << "\n";

	return 0;
}

next_permutation 구할 때 
- 살아남은 치킨집 하나 구하고 집들과 거리 구하는게 아니라
- 살아남은 치킨집들 전부 구하고 집과의 거리 구해야함

 

 

Python)

1. 백트래킹

import sys
read = sys.stdin.readline

houses = []     # 집들 위치
chicken = []    # 치킨집 위치

visited = [False] * 15      # 치킨집 폐업 여부 저장
survivors = []              # 치킨집 최대 13개

ans = 987654321             # 도시의 치킨거리

n, m = map(int, read().rstrip().split())

for i in range(n):
    temp = list(read().rstrip().split())

    # 입력 받으면서 집과 치킨집 위치 구하기
    for j in range(n):
        if temp[j] == '1':
            houses.append((i,j))
        elif temp[j] == '2':
            chicken.append((i,j))

def func(cnt, idx):
    global ans
    
    # 폐업할 치킨집을 m개 골랐으니 각 집들의 치킨 거리를 구한다.
    if cnt == m:
        sum = 0

        # 각 집들의
        for house in houses:
            r1, c1 = house[0], house[1]
            temp = 987654321

            # 치킨거리를 구해서
            for r2, c2 in survivors:
                temp = min(temp, abs(r2-r1)+abs(c2-c1))
            
            # 도시의 치킨거리를 구한다
            sum += temp 

        ans = min(ans, sum)
        return
    
    for i in range(idx, len(chicken)):
        if not visited[i]:
            survivors.append(chicken[i])
            visited[i] = True
            func(cnt+1, i+1)
            visited[i] = False
            survivors.pop()

func(0, 0)
print(ans)

 

 

 

2. from itertools import combinations

import sys
from itertools import combinations
read = sys.stdin.readline

arr = []        # 지도
houses = []     # 집들 위치
chicken = []    # 치킨집 위치

n, m = map(int, read().rstrip().split())

ans = 987654321             # 도시의 치킨거리

for i in range(n):
    arr.append(list(read().rstrip().split()))

    # 입력 받으면서 집과 치킨집 위치 구하기
    for j in range(n):
        if arr[i][j] == '1':
            houses.append([i,j])
        elif arr[i][j] == '2':
            chicken.append([i,j])

for survivors in list(combinations(chicken, m)):
    sum = 0

    # 각 집들의
    for house in houses:
        r1, c1 = house[0], house[1]
        temp = 987654321

        # 치킨거리를 구해서
        for survivor in survivors:
            r2, c2 = survivor[0], survivor[1]
            temp = min(temp, abs(r2-r1)+abs(c2-c1))
        
        # 도시의 치킨거리를 구한다
        sum += temp 

    ans = min(ans, sum)

print(ans)

c++ next_permutation 보다 직관적이어서 좋다.

시간은 1번처럼 백트래킹으로 푼 풀이가 2배 정도 더 빨랐음.