본문 바로가기
알고리즘 문제풀이/백준

[백준 15686] 치킨 배달

by m2162003 2020. 12. 16.

www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

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

 

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

처음에 틀렸던 코드는

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

댓글