[백준 15686] 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

역시 백트래킹을 사용하는 구현문제이다. 

 

백트래킹이 끝나는 기준을 폐업한 치킨 집 수로 잡아서 백트래킹을 진행한다.

처음에 틀렸던 코드는

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;
}