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

문제는 다음과 같다.

오늘은 백준15686번 치킨 배달 문제를 풀어보도록 하자. 삼성 기출문제이다. DFS를 이용해서 치킨집들을 M개만큼 조합으로 선택해야한다. 그리고 집들을 기준으로 선택한 치킨집들의 거리 중 최솟값을 찾아 더해주기만 하면 된다.

주석으로 처리된 부분을 보고 이해해보자~

                                     [코드]
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

int map[51][51];
bool visit[51][51];
int N, M, answer = 987654321;
struct pos {
	int y;
	int x;
};
vector<pos>chickens;

int CalculateDist(int y, int x) {
	int INF = 987654321;
	for (int i = 0; i < chickens.size(); i++) {
		INF = min(INF, abs(y - chickens[i].y) + abs(x - chickens[i].x));
	}
	return INF;
}

void SelectChicken(int y, int x, int cnt) {
	if (cnt == M) {
		int temp = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map[i][j] == 1) {
					temp += CalculateDist(i, j);
				}
			}
		}
		answer = min(temp, answer);
		return;
	}
	for (int i = y; i <= N; i++) {
		for (int j = x; j <= N; j++) {
			if (map[i][j] != 2 || visit[i][j])continue; //치킨집이 아니거나 이미 방문한 치킨집이면 ?
			chickens.push_back({ i,j }); //좌표 푸쉬
			visit[i][j] = true;
			SelectChicken(i, j, cnt + 1);//재귀
			chickens.pop_back();//해제
			visit[i][j] = false;
		}
		x = 1;
	}
}

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

	cin >> N >> M;//맵 크기, 치킨집 갯수
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];//맵 입력
		}
	}
	SelectChicken(1, 1, 0);
	cout << answer;
}