[백준] 15686번 - 치킨 배달

백준 온라인 저지에 수록되어있는 문제의 설명과 풀이 및 소스 코드를 작성한 글입니다.

💡 문제

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

---

💡 풀이

먼저 시간복잡도를 구해보자.

1. 전체 치킨 집 X개 중 M개를 선택하는 경우의 수 = $XCM$
2. 치킨 집과 집과의 거리 계산 = $2N*M$

결국 시간복잡도는 다음과 같다.

2≤N≤50, 1≤M≤13로 주어진 범위에 의해 최대인 경우를 구해보면 다음과 같다.

따라서 이 치킨 배달 문제는 1초 내에 충분히 완전 탐색으로 풀 수 있는 브루트 포스 문제이다.

이 문제의 풀이는 총 3단계로 나누어진다.

1) 치킨 집과 집의 위치를 기록한다.

2) 전체 치킨 집 중에서 M개를 선택하는 조합을 구한다. 이는 순열 또는 재귀함수으로 구현할 수 있다.

3) 치킨 집과 집의 거리를 계산하여 치킨 거리의 최솟값을 구한다.

---

💡 소스 코드

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

int map[51][51];
int n, m;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;

// 두 점 사이의 거리를 측정하는 함수
int distance(pair<int, int> loc1, pair<int, int> loc2) {
	int dist = 
		abs(loc1.first - loc2.first)
		+ abs(loc1.second - loc2.second);

	return dist;
}

int main() {
	// 입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	// 치킨집과 집의 좌표 구하기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 2) {
				chicken.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 1) {
				house.push_back(make_pair(i, j));
			}
		}
	}

	// 순열을 통해 모든 조합 구하기
	vector<int> p(chicken.size(), 0); // 치킨집의 개수 만큼의 길이를 가진 벡터 생성, 0으로 초기화

	for (int i = 0; i < m; i++)
		p[i] = 1; // 선택할 치킨집의 개수인 M개를 1로 설정

	sort(p.begin(), p.end());

	int total_distance = -1;

	// 순열
	do {
		int sum = 0;
		for (int i = 0; i < house.size(); i++) {
			vector<int> dists; 
			for (int j = 0; j < chicken.size(); j++) {
				if (p[j] == 0) continue; // 0인 경우는 패스

				// 1인 경우
				int dist = distance(chicken[j], house[i]); // 거리 측정
				dists.push_back(dist);
			}
			sum += *min_element(dists.begin(), dists.end()); // 측정한 치킨거리의 최솟값 저장
		}
		
		if (total_distance == -1 || total_distance > sum) 
			total_distance = sum;

	} while (next_permutation(p.begin(), p.end()));
	
	// 정답 출력
	cout << total_distance << '\n';

 	return 0;
}

---

💡 풀이 후기

반복문을 사용하여 푼다면 코드가 너무 길고 더러워질 것이다. 13중 for문을 사용해야한다. 따라서 재귀함수나 순열을 이용하는 방법이 훨씬 낫다. 치킨 집을 선택하는 조합을 구현하는 것이 핵심인 문제이다.