[Algorithm][C++] BOJ 15686 치킨 배달

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

15686번: 치킨 배달

 

풀이 핵심

1. Back Tracking 문제

 

2. home, chicken 백터 생성 (1일 경우 r, c home에 저장 / 2일 경우 r, c chicken에 저장)

 

3. solve 재귀 함수 구현 (전달 인자: 선택한 치킨집 개수 - cnt, 넣을 chicken집 인덱스 - idx)

• idx 가 chicken.size() 보다 크면 종료
• cnt가 M 일 때 (선택한 치킨집 M개 - 문제에서는 최대 M개 선택할 수 있다고 했지만 무조건 M개 선택하는 것이 가장 최소 치킨 거리가 된다) 선택한 치킨집과 집의 거리를 비교해 치킨 거리를 각 집마다 모두 구하고 더한다. 이를 ans와 비교한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
struct POS { int r, c; }; // 위치 정보
vector<POS> home, chicken;
vector<int> pick; // 선택한 치킨집 인덱스 저장
int ans = 250 * 130;

void solve(int cnt, int idx) {
	if (idx > (int)chicken.size()) return;
	if (cnt == M) {
		int candi = 0;
		for (int i = 0; i < (int)home.size(); i++) {
			int chicken_length = 250;
			for (auto j : pick) {
				chicken_length = min(chicken_length, abs(home[i].r - chicken[j].r) + abs(home[i].c - chicken[j].c));
			}
			candi += chicken_length;
		}
		ans = min(ans, candi);
		return;
	}

	pick.push_back(idx);
	solve(cnt + 1, idx + 1);
	pick.pop_back();
	solve(cnt, idx + 1);
}

int main() {
	scanf("%d %d", &N, &M);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			int tmp;
			scanf("%d", &tmp);
			if (tmp == 1) home.push_back({ r,c });
			else if (tmp == 2) chicken.push_back({ r,c });
		}
	}
	solve(0, 0);
	printf("%d", ans);
	return 0;
}

 

C++ auto (타입 추론 기능)

auto 키워드는 C++ 11에서 추가된 기능으로 굉장히 유용하다.

auto 키워드를 사용하면 초기값 형식에 맞춰 선언하는 인스턴스(변수)의 형식이 자동으로 결정된다. 이를 타입 추론 (type inference) 라고 한다.

 

auto d = 5.0; // 5.0 is a double literal, so d will be type double

auto i = 1 + 2; // 1 + 2 evaluates to integer, so i will be type int

 

함수의 전달 인자 (argument) 에는 사용할 수 없지만 return 값에 대해서는 사용 가능하다.

 

int add(auto a, auto b) { return a + b; } // 불가능

auto add(int a, int b) { return a + b; } // 가능

 

C++ 11 지역 변수를 선언할 때 사용 되었으나 C++ 11 이후 이전에는 이런 식으로 타입을 추론하는 기능으로 많이 사용되어 진다. 함수 포인터, 구조체, 공용체 및 클래스도 될 수 있다.

 

가장 재미있었던 기능은 for 문에 vector container와 활용될 때 자동적으로 vector 요소 개수 만큼 loop를 실행하며 vector 인덱스 순서대로 값이 들어간다.

 

for (auto j : pick) ...

 

for (int j = 0; j < (int)pick.size(); j++) ...

 

이 두 for문은 같은 횟 수 만큼 loop를 돌지만 j에 것은 완전히 다르다.

auto 키워드를 사용한 for 문에서의 j 는 pick[0], pick[1], pick[2], ... 이고 두 번째 for 문에서의 j 는 단순한 인덱스이다.