[Baekjoon] 15686. 치킨 배달

Luna Park·2023년 3월 10일
1
post-thumbnail

문제링크

NxN 2차원 배열에서 치킨집을 M개 골라 도시의 치킨 거리를 최소값으로 만드는 문제이다.
여기서 치킨 거리집과 가장 가까운 치킨집 사이의 거리이고, 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
치킨 거리는 |x1-x2| + |y1-y2|로 구할 수 있다.

두 좌표만 알면 거리를 구할 수 있기에 굳이 BFS를 쓰지 않아도 됬었는데, 습관적으로 쓰다가 시간 초과가 나버려 문제를 푸는데 시간이 조금 더 걸렸다.

코드는 아래와 같다.

  1. 치킨 집 중에서 M개를 선택한다.
  2. 선택된 치킨집 중 각각의 집으로부터 가장 가까운 치킨집까지의 거리를 구해서 더한다.
  3. 합이 최소인 경우를 구한다.
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int N, M;
int myMap[50][50];
bool visited[50][50];
int dist[50][50];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct p
{
    int x;
    int y;
};

p make_p(int x, int y)
{
    p temp;
    temp.x = x;
    temp.y = y;
    return temp;
}

vector<p> chicken;
vector<p> house;

int arr[15];
int answer;

void select_chicken(int idx)
{
    if (idx == M)
    {
        vector<p> selected;
        for (int i = 0; i < M; i++)
        {
            selected.push_back(chicken[arr[i]]);
        }

        int sum = 0;

        for (int i = 0; i < house.size(); i++)
        {
            int min = INT16_MAX;

            for (int j = 0; j < selected.size(); j++)
            {
                int dis = abs(house[i].x - selected[j].x) + abs(house[i].y - selected[j].y);
                if (dis < min)
                    min = dis;
            }

            sum += min;
        }

        if (sum < answer)
            answer = sum;
    }
    else
    {
        for (int i = 0; i < chicken.size(); i++)
        {
            if (idx == 0 || arr[idx - 1] < i)
            {
                arr[idx] = i;
                select_chicken(idx + 1);
            }
        }
    }
}

int main()
{
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int x;
            cin >> x;

            if (x == 2)
                chicken.push_back(make_p(i, j));

            if (x == 1)
                house.push_back(make_p(i, j));
        }
    }

    answer = INT16_MAX;
    select_chicken(0);

    cout << answer << endl;
}
profile
Happy Ending Is Mine

0개의 댓글