[C++] BOJ 15686번: 치킨 배달

문제 링크

문제 풀이

문제에 주어진 조건을 그대로 시뮬레이션하는 방식으로 문제를 풀었다. 이 문제는 특이하게도 값을 입력받을 때에 모든 좌표의 각 해당 위치의 값을 기록할 필요 없이, 집(1)과 치킨집(2)의 위치만 저장하여도 문제를 풀어낼 수 있다. 아래의 코드는 다음의 순서대로 구현되었다.

 

1. 입력받은 값을 통해 집과 치킨집의 위치를 기록

2. 도시의 모든 치킨집들 중 M개의 치킨집을 선택

2번의 예: M이 3이고 치킨집이 A,B,C,D가 있을 경우 [A,B,C를 선택 / A,C,D를 선택 / B,C,D를 선택]하는 3가지 경우가 생겨남

3. 선택한 치킨집에 대한 각 집의 치킨 거리를 계산

4. 구한 치킨 거리들을 이용해 도시의 치킨 거리를 계산

5. 기존의 도시의 치킨 거리 값보다 새로운 도시의 치킨 거리 값이 작을 경우 값을 새로 갱신

6. 2번 과정부터 5번 과정을 모든 경우의 수를 따질 때까지 반복

 

전역변수 result의 초기값과 calcChickenDistances 함수의 checkDistances[homePointIdx]의 값을 9999로 지정한 이유는 치킨 거리와 도시의 치킨 거리의 최대값이 9999보다 작기 때문이다. 코드를 보면 기존의 result 값보다 새로 계산한 result 값이 작을 경우 result 변수가 가지고 있는 값을 새로 계산한 값으로 바꾸어 주기 때문에 result에 초기값으로 엄청 큰 수를 주어야만 값이 올바르게 갱신될 수 있다.

 

도시의 크기가 N * N이라고 하였을 때 치킨 거리의 최대값은 (1, 1)과 (N, N) 사이의 거리인 |N-1| + |N-1|이고, 2 ≤ N ≤ 50이므로 치킨 거리의 최대값은 2N-2 = 100-2 = 98이 된다. 도시의 치킨 거리의 최대값은 치킨 거리의 최대값 * M보다 작으므로 98 * 13 = 1274보다 작은 값을 갖게 된다. 정확하게 코드를 작성하기 위해서는 calcChickenDistances 함수에서 checkDistances[homePointIdx]의 값을 99, result의 초기값을 1275 정도로 주는 것이 맞겠지만 두 값(99, 1275)보다 큰 9999로 해도 결과에는 변함이 없다.

코드

#include <iostream>
#include <vector>
#include <utility>

#define EMPTY 0
#define HOME 1
#define CHICKEN_RESTAURANT 2

using namespace std;

int N, M;

int chickenDistances[110];
int result = 9999;
vector<pair<int, int>> chickenRestaurantPoints;
vector<pair<int, int>> homePoints;
int chosenRestaurantIndexes[31];

void calcChickenDistances()
{
    for (int homePointIdx = 0; homePointIdx < homePoints.size(); homePointIdx++)
    {
        chickenDistances[homePointIdx] = 9999;

        pair<int, int> homePoint = homePoints[homePointIdx];

        int yp = homePoint.first;
        int xp = homePoint.second;

        for (int i = 0; i < M; i++)
        {
            int chosenIndex = chosenRestaurantIndexes[i];
            int restaurantPointY = chickenRestaurantPoints[chosenIndex].first;
            int restaurantPointX = chickenRestaurantPoints[chosenIndex].second;

            int numForDist1 = restaurantPointY - yp;
            int numForDist2 = restaurantPointX - xp;

            if (numForDist1 < 0)
                numForDist1 = -numForDist1;
            if (numForDist2 < 0)
                numForDist2 = -numForDist2;
            int distance = numForDist1 + numForDist2;
            if (chickenDistances[homePointIdx] > distance)
                chickenDistances[homePointIdx] = distance;
        }
    }
}

void calcResult(int depth, int index)
{
    if (depth == M)
    {
        int chickenDistanceOfCity = 0;
        calcChickenDistances();
        for (int i = 0; i < homePoints.size(); i++)
            chickenDistanceOfCity += chickenDistances[i];
        if (chickenDistanceOfCity < result)
            result = chickenDistanceOfCity;
        return;
    }
    for (int i = index + 1; i < chickenRestaurantPoints.size(); i++)
    {
        chosenRestaurantIndexes[depth] = i;
        calcResult(depth + 1, i);
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int input;

    cin >> N >> M;

    for (int yp = 1; yp <= N; yp++)
    {
        for (int xp = 1; xp <= N; xp++)
        {
            cin >> input;
            if (input == CHICKEN_RESTAURANT)
                chickenRestaurantPoints.push_back({yp, xp});
            else if (input == HOME)
                homePoints.push_back({yp, xp});
        }
    }

    calcResult(0, -1);

    cout << result << '\n';

    return 0;
}