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

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

15686번: 치킨 배달

🔔 문제 : 

(2<=N<=50)인 NxN 크기의 좌표가 있습니다.

이후, 각 좌표마다 값이 주어집니다. 0은 거리, 1은 집, 2는 치킨집입니다.

 

집에서 가까운 치킨집의 거리가 치킨거리라고 합니다.

예를 들어 집(1,1)  치킨집(3,1) 이라고 칭하면 치킨거리는 |3-1| + |1-1| = 2가 됩니다.

 

이 집들의 치킨거리 합이 "도시의 치킨거리" 가 됩니다. 

 

또한 치킨집을 (1<= M <= 13)인 M개로 고정시킬 예정인데, 도시의 치킨거리의 최솟값을 출력하는 문제입니다.

 

입력값으로  N, M 값 이후 도시의 좌표 값이 주어집니다.

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

---

🔔 Kick Point :

저는 DFS의 백트래킹 + 조합 방식을 사용하여 구하였습니다. ( 백트래킹 + 조합 DFS)

 

우선, 치킨집을 조합방식을 통해 M개를 선정후, 그 치킨집의 x좌표와, y좌표를 저장합니다.

이후에 각 집을 돌아가면서, 치킨거리의 최솟값을 합해서 도시의 치킨거리를 구하면 됩니다.

 

여기서 킥 포인트는, DFS 백트래킹을 시도할 때, 2차원 배열로 치킨집을 돌아야하는 것을 1개 for문을 통하여 순회 할 수 있었다는 점입니다.

 

치킨거리를 구할 때, for문을 많이 써서 가독성이 좀 떨어지는듯해요 ㅠㅠ.. 다음에는 2차원 배열을 1차원으로 구현해야겠어요

 

---

🔔 Code :

#include <iostream>
#include <cmath>
using namespace std;

int n, m; // (n, n) 치킨집 m개
int city[51][51];
int xChickenShop[13];
int yChickenShop[13];
int MIN = 10000;

int chickenStreet() {

	int r = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int t = 10000;
			if (city[i][j] == 1) {
				for (int k = 0; k < m; k++) {
					int tmp = abs(xChickenShop[k] - i) + abs(yChickenShop[k] - j);
					t = tmp < t ? tmp : t;
				}
				r += t;
			}
		}
	}
	return r;
}

void DFS(int cnt =0, int k =0) {
	if (cnt == m) {
		int tmp = chickenStreet();
		MIN = MIN > tmp ? tmp : MIN;
		return;
	}
	
	for (int i = k; i < n*n; i++) {
		int x = i % n;
		int y = i / n;
		x++, y++;
		
		if (city[x][y] == 2) {
			xChickenShop[cnt] = x;
			yChickenShop[cnt] = y;
			DFS(cnt + 1, i + 1);
		}
	}


}


int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> city[i][j];
		}
	}
	DFS();
	cout << MIN;
}

---