최적의 경우를 출력하는 것입니다.
그래서 아래의 코드를 적었습니다.
#include <bits/stdc++.h>
using namespace std;
#define EMPTY 0
#define HOME 1
#define CHICKEN 2
int n;
int m;
int **board;
int score = 999999999;
class Coord
{
public:
int cX, cY;
Coord() : Coord(0, 0)
{}
Coord(int x_, int y_) : cX(x_), cY(y_)
{}
};
class Node
{
public:
vector<Coord> coords; //치킨 집을 최대 m개만 저장한다.
Node()
{}
Node(vector<Coord> coords_) : coords(coords_)
{}
};
vector<Coord> home;
vector<Coord> chicken;
int GetDistance(Coord lhs, Coord rhs)
{
int dx = lhs.cX - rhs.cX;
int dy = lhs.cY - rhs.cY;
if (dx < 0)
{
dx = dx * -1;
}
if (dy < 0)
{
dy = dy * -1;
}
return dx + dy;
}
bool* flag;
void GetChickenDistance(Node tmp_node)
{
int total_score = 0;
int local_score = 999999999;
for (int j = 0; j < home.size(); j++)
{
for (int i = 0; i < tmp_node.coords.size(); i++)
{
int value = GetDistance(home[j], tmp_node.coords[i]);
if (local_score > value)
{
local_score = value;
}
}
total_score += local_score;
local_score = 999999999;
}
if (score > total_score)
score = total_score;
}
void DFS(int n_, int k)
{
if (n_ == k) //남은 0~n을 모두다 true로 한다.
{
Node tmp_node;
for (int i = 0; i < n_; i++)
{
flag[i] = true;
}
for (int i = 0; i < chicken.size(); i++)
{
if (flag[i] == true)
{
tmp_node.coords.push_back(chicken[i]);
}
}
//tmp_node에 있는 치킨집과 home을 통해 치킨 거리를 계산한다.
GetChickenDistance(tmp_node);
for (int i = 0; i < n_; i++)
{
flag[i] = false;
}
return;
}
else if (k == 1) //남은 0~n중 하나만 true 이다.
{
for (int j = 0; j < n_; j++)
{
Node tmp_node;
flag[j] = true;
for (int i = 0; i < chicken.size(); i++)
{
if (flag[i] == true)
{
tmp_node.coords.push_back(chicken[i]);
}
}
flag[j] = false;
//치킨거리 계산
GetChickenDistance(tmp_node);
}
return;
}
flag[n_ - 1] = true;
DFS(n_ - 1, k - 1);
flag[n_ - 1] = false;
DFS(n_ - 1, k);
}
int main(void)
{
scanf("%d %d", &n, &m);
int input;
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
scanf("%d", &input);
if (input == HOME)
{
home.push_back(Coord(i, j));
}
else if (input == CHICKEN)
{
chicken.push_back(Coord(i, j));
}
}
}
/*
board = new int*[n];
for (int i = 0; i < n; i++)
{
board[i] = new int[n];
//memset(board[i], 1, n*sizeof(int));
}
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
scanf("%d", &board[j][i]);
if (board[j][i] == HOME)
{
home.push_back(Coord(i, j));
}
else if (board[j][i] == CHICKEN)
{
chicken.push_back(Coord(i, j));
}
}
}
*/
flag = new bool[chicken.size()];
for (int i = 0; i < chicken.size(); i++)
{
flag[i] = false;
}
DFS(chicken.size(), m);
printf("print : %d\n", score);
return 0;
}
치킨집과 가정집 사이의 치킨거리를 구한다.
가정집과 선별된 치킨집 간에 치킨거리 연산을 GetDistance 함수를 통해 서로서로다 수행하고 최소 치킨거리를 구한다.
combination을 통해서 치킨집을 선별하는 함수. 선별이 끝나자 마자 GetChickenDistance 함수로
선별된 치킨집을 통해 얻을 수 있는 최소 치킨거리를 계산한다.
크게 3가지 함수로 이루어저 있습니다.
가 나오네요...
출력이 어떤식으로 잘못된건지 알려주질 않으니 어디서부터 고쳐 나가야 할지 조차 모르겠습니다.
너무 답답하네요 ㅠㅠ.....
