[BOJ-15686] 치킨배달

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

15686번: 치킨 배달

 

모 기업 코딩테스트 문제입니다.

 

사실, 이 문제의 앞부분을 읽다보면 이상한 부분에 핀트가 꽂힐 수 있지만, dfs와 백트래킹으로 조합을 구현해본 경험이 있다면 쉽게 풀 수 있는 문제입니다.

 

dfs를 이용해 백트래킹 해가면서 모든 경우의 수를 조합해 완전탐색하고, 그 중 치킨거리가 최소가 될 때의 값을 출력해주면 됩니다.

 

-문제 풀이

1. 입력을 받습니다.

 - 입력 받는 값이 1일 경우 집 -> 집의 좌표를 담는 벡터에 이 값들을 저장해줍니다.

 - 입력 받는 값이 2일 경우 치킨집 -> 치킨집의 좌표를 담는 벡터에 이 값들을 저장해줍니다.

 

2. dfs 함수를 실행합니다.

 - 시작 : 매개변수로 가장 처음 값을 주고 모든 치킨집을 탐색할 준비를 합니다.

 - 선택한 치킨집이 m일 경우 -> 모든 집에 대하여 선택한 치킨집 과의 치킨 거리를 구합니다.

 - 아닐 경우 -> 선택한 치킨집이 m이 되도록 재귀적으로 함수를 실행합니다.

 - 치킨거리를 구하고 난 뒤 함수를 return하고 선택한 치킨집을 pop_back()하여 다음 치킨집을 다시 선택합니다.

 - 위 과정을 반복합니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

struct POSITION {
	int y, x;
};
using namespace std;

int n, m, res;
int map[51][51];
vector<POSITION> vec, sel, shop;

void dfs(int node) {
	if (sel.size() == m) {

		int candi = 0;
		for (int i = 0; i < vec.size(); i++) {
			int dist = 0x7fffffff;
			for (int j = 0; j < sel.size(); j++) {
				dist = min(dist, abs(vec[i].y - sel[j].y) + abs(vec[i].x - sel[j].x));
			}
			candi += dist;
		}

		if (res > candi) res = candi;
		return;
	}

	for (int i = node; i < shop.size(); i++) {
		sel.push_back(shop[i]);
		dfs(i + 1);
		sel.pop_back();
	}
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			scanf("%d", &map[y][x]);

			if (map[y][x] == 1) {
				vec.push_back({ y,x });
			}
			else if (map[y][x] == 2) {
				shop.push_back({ y,x });
			}
		}
	}

	res = 0x7fffffff;
	dfs(0);

	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}