알고리즘 문제풀이:: 백준 삼성SW 15686 치킨 배달

백준 풀이 - DFS / 조합

문제리뷰

15686 치킨 배달 (골드5)

 

피드백

DFS로 치킨 가게의 조합을 구한 후,

각 치킨 가게에서 집까지의 거리를 구해

최솟값을 구하면 되는 문제

 

가장 처음 풀 때는 치킨가게까지 BFS로 구하려다가 꼬였는데 그냥 좌표로 계산하면 간단한 문제였음

• 이중 for문 인덱스 주의
• 입력값을 for문에 사용할 때 의미를 제대로 알고 사용해야 실수하지 않음
  • m은 남길 치킨 가게의 개수인데 치킨 가게의 총 개수로 착각해서 헤맸음

---

 

C++

15686 치킨 배달

#include <iostream>
#include <vector>
#include <deque>
#define MAX 50
#define X first
#define Y second
using namespace std;

struct PLACE {
	int x;
	int y;
	int dist;

	PLACE(int _x, int _y, int _dist) {
		x = _x;
		y = _y;
		dist = _dist;
	}
};

int n, m, answer;
int vis[13];
int board[MAX][MAX];
vector< pair<int, int> > chicken;
vector<PLACE> house;

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];

			if (board[i][j] == 2) {
				chicken.push_back({ i, j });
			}
			else if (board[i][j] == 1) {
				house.push_back(PLACE(i, j, 0));
			}
		}
	}
}

int abs(int a, int b) {
	return (a > b) ? a - b : b - a;
}

void calDist() {
	for (int i = 0; i < house.size(); i++) {
		house[i].dist = 0;
	}

	for (int i = 0; i < chicken.size(); i++) {
		if (!vis[i]) continue;

		pair<int, int> ch = chicken[i];
		for (int j = 0; j < house.size(); j++) {
			PLACE h = house[j];
			int temp = abs(ch.X, h.x) + abs(ch.Y, h.y);

			if (h.dist == 0 || h.dist > temp) {
				house[j].dist = temp;
			}
		}
	}
}

void calAns() {
	int temp = 0;
	for (int i = 0; i < house.size(); i++) {
		temp += house[i].dist;
	}

	if (answer == 0 || answer > temp)
		answer = temp;
}

void dfs(int start, int cnt) {
	if (cnt == m) {
		calDist();
		calAns();
		return;
	}

	for (int i = start; i < chicken.size(); i++) {
		if (vis[i]) continue;		
		vis[i] = 1;
		dfs(i, cnt + 1);
		vis[i] = 0;
	}
}

void solution() {
	dfs(0, 0);
}

void solve() {
	input();
	solution();
}

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

	solve();
	cout << answer << '\n';
}