역시 백트래킹을 사용하는 구현문제이다.
백트래킹이 끝나는 기준을 폐업한 치킨 집 수로 잡아서 백트래킹을 진행한다.
처음에 틀렸던 코드는
void BackTracking(int cnt)
{
if (cnt == sze_c - m)
{
int distance = getDistance();
result = min(result, distance);
return;
}
for (int i = cnt; i < sze_c; i++)
{
closed[i] = 1;
BackTracking(cnt + 1);
closed[i] = 0;
}
}
cnt만 인자로 받아서 처리했는데 그러면 BackTracking(cnt+1) 부분이 문제가 된다. 현재 폐업한 치킨집 이후의 치킨집만 확인하는게 본래 의도였는데 저 코드는 cnt를 받음으로써 그 기능을 하지 못한다. 그래서 현재 폐업한 치킨집을 표시하는 idx와 폐업한 치킨 집 수를 나타내는 cnt를 분리했다.
치킨 폐업이 확정되면 bfs를 사용하지 않고 바로 치킨집과 집 사이의 최소 거리를 구해준다.
#include <stdio.h>
#include <algorithm>
#include <limits.h>
using namespace std;
int n, m, sze_c, sze_h;
int result = INT_MAX;
int arr[50][50];
struct Chicken
{
int row, col;
};
struct House
{
int row, col;
};
House houses[100];
Chicken chickens[13];
int closed[13];
int getDistance()
{
int distance = 0;
for (int i = 0; i < sze_h; i++)
{
int minDis = INT_MAX;
for (int j = 0; j < sze_c; j++)
{
if (closed[j])
continue;
int tmp = abs(houses[i].row - chickens[j].row) + abs(houses[i].col - chickens[j].col);
minDis = min(minDis, tmp);
}
distance += minDis;
}
return distance;
}
void BackTracking(int idx, int cnt)
{
if (cnt == sze_c - m)
{
int distance = getDistance();
result = min(result, distance);
return;
}
for (int i = idx; i < sze_c; i++)
{
closed[i] = 1;
BackTracking(i + 1, cnt + 1);
closed[i] = 0;
}
}
int main(void)
{
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &arr[i][j]);
if (arr[i][j] == 2)
{
chickens[sze_c++] = {i, j};
}
if (arr[i][j] == 1)
{
houses[sze_h++] = {i, j};
}
}
}
BackTracking(0, 0);
printf("%d\n", result);
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 14503] 로봇 청소기 (0) | 2020.12.17 |
---|---|
[백준 14499] 주사위 굴리기 (0) | 2020.12.17 |
[백준 15683] 감시 (0) | 2020.12.16 |
[백준 2012] 등수 매기기 (0) | 2020.12.16 |
[백준 1543] 문서 검색 (0) | 2020.12.16 |
댓글