https://www.acmicpc.net/problem/15686
제가 이해한 풀이방법은
치킨집을 줄이고자 하는 수(m)까지 줄여야 하는데
Combination을 통해서 줄일 수 있는 모든 경우의 수를 다 조사하고
최적의 경우를 출력하는 것입니다.
그래서 아래의 코드를 적었습니다.
#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
치킨집과 가정집 사이의 치킨거리를 구한다.
GetChickenDistance
가정집과 선별된 치킨집 간에 치킨거리 연산을 GetDistance 함수를 통해 서로서로다 수행하고 최소 치킨거리를 구한다.
DFS
combination을 통해서 치킨집을 선별하는 함수. 선별이 끝나자 마자 GetChickenDistance 함수로
선별된 치킨집을 통해 얻을 수 있는 최소 치킨거리를 계산한다.
크게 3가지 함수로 이루어저 있습니다.
사이트에 올라와 있는 테스트케이스가 모두다 맞는것을 확인하고 제출 하였는데
"틀렸습니다"
가 나오네요...
아무래도 비공개 테스트케이스에서 잘못된 출력이 나와서 그런듯한데
대체 어디가 잘못된걸까요...??
출력이 어떤식으로 잘못된건지 알려주질 않으니 어디서부터 고쳐 나가야 할지 조차 모르겠습니다.
다른사람들 코드랑 비교해 보아도 전체적인 알고리즘도 거의 비슷하고
제가 직접 테스트케이스를 만들어서 여러 프로그램을 같이 돌려보면 출력도 같게 나오는데
뭐가틀린걸까요...??
풀소스코드를 통째로 가져와서 질문하는게 안좋은 방법인건 알고있지만
너무 답답하네요 ㅠㅠ.....
본인삭제금지
글쓰기