[백준 15686] 치킨 배달 (C++) - G5

문제

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

15686번: 치킨 배달

 

개요

문제를 처음 봤을 때 백트래킹 문제임을 바로 파악하지는 못했다.

이차원 배열이 주어져서 당연하게 DFS 혹은 BFS로 접근해야겠다고 생각했다.

백트래킹을 고려하지 않고 있었기 때문에, 여러 개의 치킨집 중에서 M개를 어떻게 선택해야 할지 고민하는 데에 시간을 굉장히 많이 썼다.

이 문제 또한 결국 구글링의 힘을 빌렸다...! (언제쯤 혼자 풀어낼 거냐..나 자신아..)

 

백트래킹 문제를 연속으로 풀면서, 여러 가지 경우의 수 중에서 M개를 선택해야 하는 문제 유형은 백트래킹 가능성이 굉장히 높다는 것을 인지하게 되었다.

 

문제 풀이

이 문제 또한 전형적인 백트래킹 문제이다.

답을 구하는 로직은 굉장히 간단하다.

여러 개의 치킨집 중에서 M개를 선택한 후, 각각의 집에 대해서 M개의 치킨집까지의 거리 중 가장 최소의 거리를 더한 것이 최종 결과값이다.

 

위의 로직에서, 여러 개의 치킨집 중에서 M개를 선택하는 과정이 곧 백트래킹을 사용해야 함을 나타내고 있다.

 

일단, pair<int, int> 타입으로 house, chicken, picked 3개의 vector를 전역변수로 선언해주었다.

house는 집(1)의 좌표, chicken은 치킨집(2)의 좌표, picked는 치킨집들 중에서 M개에 선택된 치킨집의 좌표를 저장하는 역할이다.

그리고, 이차원 배열을 입력받는 과정에서, 1인 경우는 house에, 2인 경우는 chicken에 저장해주었다.

(굳이 이차원 배열을 선언해서 모든 값을 저장할 필요가 없다.)

 

그리고, 백트래킹을 위한 함수 func를 선언해준다.

여태까지 백트래킹 문제를 풀어본 바로는, 백트래킹 함수 func는 거의 항상 다음과 같은 형태를 갖는다.

1. 인자로 idx, cnt를 포함한다.

 (idx : 배열 또는 벡터에서 원소를 탐색하는 포인터 역할 / cnt : 여러 경우의 수 중에서 문제 조건으로 주어진 특정 횟수까지 카운팅하는 용도, 탈출조건에 사용됨)

2. if문을 이용한 탈출 조건 + return

3. func 함수를 재귀적으로 타고 들어가는 부분 + 앞뒤로 방문 여부 true/false 전환 + vector 원소 push_back/pop_back

 

일단 func 함수를 재귀적으로 타고 들어가는 부분을 먼저 구현한 다음에, 탈출 조건 부분을 구현하는 것이 더 편한 것 같다.

func 함수를 재귀적으로 타고 들어가는 부분은 다음과 같다.

for (int i = idx; i < chicken.size(); i++) {
	if (check[i]) continue;
		
	check[i] = true;
	picked.push_back(chicken[i]); // 치킨집 중에서 선택
	func(i, cnt + 1);
	check[i] = false;
	picked.pop_back();
}

위의 for문에서 가장 중요한 점은 for문의 시작값에 idx를 사용한다는 것이다.

애초에 idx는 이 용도를 위해 사용되는 인자이다.

for문 내의 func 함수에 현재 i를 넘겨줌으로써, 타고 들어간 func 함수에서는 이 i가 idx 역할을 하게 된다.

그래서 굳이 매번 i = 0부터 탐색할 필요 없이 이전 마지막 위치부터 확인함으로써 효율성을 높이는 것이다.

idx를 사용하지 않고, i = 0부터 탐색하게 되면 시간 초과가 뜰 가능성이 높다.

 

탈출 조건 부분은 다음과 같다.

if (cnt == m) { // 탈출 조건
	int sum = 0; // 하나의 경우의 최종 결과 (중간 정답)
	for (int i = 0; i < house.size(); i++) { // 모든 집에 대해서 min_dist 구함
		int min_dist = INF;
		for (int j = 0; j < picked.size(); j++) { // 선택된 M개의 치킨집들에 대해 최소 거리를 구함
			min_dist = min(min_dist, distance(house[i], picked[j]));
		}
		sum += min_dist;
	}
	ans = min(ans, sum); // 중간 정답인 sum인 최종 정답인 ans와의 비교를 거쳐야 함
	return;
}

이 문제는 특히 까다로웠던 것이, min 함수를 2번이나 사용해야 했다.

 

각각의 집에 대해서 M개의 치킨집까지의 거리 중에서 최소 거리를 구하는 과정에서 min을 한 번 사용한다.

그리고, 각 집의 최소 거리를 더한 중간 정답 sum을 구한다.

그런데, 이 경우는 여러 개의 치킨집 중에서 M개를 선택하는 경우의 수 중에 하나의 경우일 뿐이다.

M개를 선택하는 나머지 경우에 대해서도 똑같은 과정을 진행하게 될 것이다.

모든 경우를 다 진행한 후에 도출되는 최종 정답이 ans이다.

그래서, 각 경우에 대해 중간 정답 sum과 최종 정답 ans를 비교하는 과정이 필요하고, 이 때 min을 한 번 더 사용한다.

 

그리고, min을 사용하는 경우에는 사용될 변수를 처음에 엄청 큰 값으로 설정해놓아야 한다.

일반적으로, #define을 통해 INF라는 변수에 이 큰 값을 설정해놓는다.

#define INF (~0U >> 2) // 약 10억 7천만 (1073741823)

나는 (~0U >> 2)를 사용하였다.

0U는 unsigned int 0을 의미하고, ~는 NOT을 의미한다.

0U는 32개의 0으로 이루어져 있고, ~에 의해 32개의 1로 뒤집힌다.

그리고 shift 연산자 >>와 숫자 2에 의해 비트를 오른쪽으로 2번 shift함으로써, 앞의 두 비트는 0이고, 나머지 30개의 비트는 1으로 이루어진 32비트짜리 숫자가 되는 것이다.

즉, 2^0부터 2^29까지 모두 더한 값이므로, 2^30 - 1 = 1073741823, 약 10억 7천만의 값을 가진 숫자이다.

이 숫자의 좋은 점은 INF + INF를 해도 2^31 - 2이어서 int의 최대 범위인 2^31 - 1보다 빈틈없게 작다는 점이다.

다만, 이 숫자가 기억나지 않을 때에는 통상적으로 사용하는 987654321를 사용해도 큰 상관은 없을 것이다.

 

코드

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

#define INF (~0U >> 2) // 약 10억 7천만 (1073741823)

using namespace std;

int n, m;
int ans = INF; // 최종 정답
vector<pair<int, int>> house; // 집 좌표
vector<pair<int, int>> chicken; // 치킨집 좌표
vector<pair<int, int>> picked; // M개에 선택받은 치킨집 좌표
bool check[13]; // check 배열의 인덱스는 chicken 배열의 인덱스와 매칭


int distance(pair<int, int> a, pair<int, int> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}

void func(int idx, int cnt) { // idx : 
	if (cnt == m) { // 탈출 조건
		int sum = 0; // 하나의 경우의 최종 결과 (중간 정답)
		for (int i = 0; i < house.size(); i++) { // 모든 집에 대해서 min_dist 구함
			int min_dist = INF;
			for (int j = 0; j < picked.size(); j++) { // 선택된 M개의 치킨집들에 대해 최소 거리를 구함
				min_dist = min(min_dist, distance(house[i], picked[j]));
			}
			sum += min_dist;
		}
		ans = min(ans, sum); // 중간 정답인 sum인 최종 정답인 ans와의 비교를 거쳐야 함
		return;
	}
	for (int i = idx; i < chicken.size(); i++) {
		if (check[i]) continue;
		
		check[i] = true;
		picked.push_back(chicken[i]); // 치킨집 중에서 선택
		func(i, cnt + 1);
		check[i] = false;
		picked.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int num; cin >> num;
			if (num == 1) house.push_back({ i, j });
			if (num == 2) chicken.push_back({ i, j });
		}
	}
	dfs(0, 0);
	cout << ans;
	return 0;
}

 

깨달은 점

백트래킹 문제를 연속으로 풀면서 공통적으로 발견되는 패턴이 있음을 인지할 수 있었다.

또한, 탈출 조건을 구현할 때에 생각보다 그 내용이 길어지는 경우가 많은데 이 부분을 따로 함수로 빼서 구현할지 아니면 원래대로 if문 안에 다 구현하는게 나을지는 비슷한 유형을 많이 풀어보면서 나한테 더 편하고 직관적인 방식을 선택해야겠다.