[BOJ 15686] 치킨 배달

썸네일

문제 설명

15686번: 치킨 배달

문제에서 중요한 부분들을 하이라이트로 표시해보았다.

 

이제 예제를 통해 문제를 좀 더 확실히 이해해보자.

M=3인데 치킨집(2)의 개수가 3개이므로 폐업을 시킬 필요가 없다.

 

• (1,3) ~ (2,3) 사이 치킨 거리 = 1
• (3,2) ~ (3,3) 사이 치킨 거리 = 1
• (3,3) ~ (4,3) 사이 치킨 거리 = 1
• (2,3) ~ (2,5) 사이 치킨 거리 = 2

이므로, 도시 전체의 치킨 거리는 5이다.

 

구현 아이디어

• 치킨집 중 중복 없이 M개를 구해야 한다 > 조합을 사용하자.
• 도시의 치킨 거리 = 집1의 치킨 거리 + 집2의 치킨 거리 + ... > 각 집의 치킨 거리를 구하고, 그것을 합하자.
• 집의 치킨 거리를 구할 때 치킨집 1이 최소 거리인지 치킨집 2가 최소 거리인지 모른다 > 일단 다 해보고 그 중 최소값을 고르자 (min 함수 활용)
• 도시의 치킨 거리가 최소가 되기 위해서는 각 집의 치킨 거리가 최소여야 한다.

 

구현 과정을 좀 더 자세하게 적으면, 아래와 같다.

1. 도시의 정보를 입력 받을 때 집의 좌표와 치킨집의 좌표를 배열에 저장한다.
2. 치킨집 좌표 배열에서 조합을 사용하여 M개의 경우를 구한다.
3. 각 경우마다 도시의 치킨 거리를 구한다. 초기값이 INF인 변수 ret을 만들고 만약 이번 경우의 치킨 거리가 최소라면, ret을 갱신한다.

 

완전 탐색으로 풀 수 있는 이유

솔직히 말하면 ... 알고리즘 분류별로 문제를 풀고 있기 때문에 완전 탐색이라는 것을 알고 풀 수 있었다 ^ㅅ^ ...

시간 복잡도 계산은 큰돌님의 강의를 참고하여 작성하였다 ...

 

N은 최대 50이기 때문에 도시의 전체 칸은 50*50=2500이고, 치킨집은 최대 13개이기 때문에 2500C13(대충 봐도 시간 초과)이라고 생각할 수 있다.

하지만 문제에서 집은 최대 2N개라고 했으므로, 13C? * 100이 최대가 된다.

13C?가 될 수 있는 최대값은 13C6으로 1716이다.

 

그렇기 때문에 최대 연산은 약 171600회로, 완전 탐색으로 풀어도 시간 초과가 발생하지 않는다. (보통 약 1억 번의 연산까지는 시간 내에 풀 수 있다.)

구현

각 과정을 코드로 나타내보자.

 

1. 도시의 정보를 입력 받을 때 집의 좌표와 치킨집의 좌표를 배열에 저장한다.

vector<pair<int, int>> homes; // 집들의 좌표
vector<pair<int, int>> chickens; // 치킨집들의 좌표
int k;

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        cin >> k;
        // 집과 치킨집의 좌표를 배열에 저장
        if (k == 1) homes.push_back({i, j});
        if (k == 2) chickens.push_back({i, j});
    }
}

// Example
// homes - [{1,1}, {1,3}, {2,2} ...]
// chickens - [{1,2}, {1,5}, {2,1} ...]

pair 타입은 2개의 데이터를 저장할 때 사용하는 클래스로, 좌표를 저장할 때 유용하다.

 

2. 치킨집 좌표 배열에서 조합을 사용하여 M개의 경우를 구한다.

vector<int> temp; // 치킨집 M개를 고른 배열 (index를 저장)
vector<vector<int>> temps; // temp의 조합

// 조합 구현
void combi(int start, vector<int> temp) {
    if (temp.size() == m) {
        temps.push_back(temp);
        return;
    }

    for (int i = start+1; i < chickens.size(); ++i) {
        temp.push_back(i);
        combi(i, temp);
        temp.pop_back();
    }
}

// chickens에서 폐업되지 않은 치킨집 M개의 경우의 수를 구한다.
combi(-1, temp);

주의
combi 함수는 index를 저장한다.
chickens가 [{1,2}, {1,5}, {2,1}, {3,1}]이고, 임의의 경우의 수가 앞의 3개를 골랐을 때일 경우 temp는 [0, 1, 2]가 된다.
그리고 temps는 [ [0, 1, 2], [0, 1, 3], [1, 2,3] ]가 된다.

 

3. 각 경우마다 도시의 치킨 거리를 구한다. 초기값이 INF인 변수 ret을 만들고 만약 이번 경우의 치킨 거리가 최소라면, ret을 갱신한다.

// 반복문을 통해 치킨 거리를 구한다.
for (auto temp : temps) { // ex) [1,2]
    pair<int, int> c;
    int sum = 0;
    int dist;
    for (auto h : homes) { // 집을 기준으로
        int home = INF;
        for (auto elem : temp) { // 치킨 거리를 구한다.
            c = chickens[elem];
            dist = abs(h.first - c.first) + abs(h.second - c.second);
            home = min(home, dist); // 치킨 거리 최솟값 갱신
        }
        sum += home;
    }
    ret = min(ret, sum);
}

3중 반복문이 사용되었다. 반복문의 계층 구조는 아래와 같다.

• 치킨집이 M개 남은 각 경우에 대해
  • 각 집으로부터
    • 모든 치킨집까지의 거리를 구하고, 그 중 최솟값을 구하면 그것이 그 집의 최종적인 치킨 거리 최소값이다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

#define INF 10e6

int n, m; // n - 도시의 크기가 n*n, m - 폐업 X인 치킨집의 개수
vector<pair<int, int>> homes; // 집들의 좌표
vector<pair<int, int>> chickens; // 치킨집들의 좌표
vector<int> temp; // 치킨집 M개를 고른 배열 (index를 저장)
vector<vector<int>> temps; // temp의 조합
int ret = INF; // 도시의 치킨 거리

void combi(int start, vector<int> temp) {
    if (temp.size() == m) {
        temps.push_back(temp);
        return;
    }

    for (int i = start+1; i < chickens.size(); ++i) {
        temp.push_back(i);
        combi(i, temp);
        temp.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    // 입력
    int k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> k;
            // 집과 치킨집의 좌표를 배열에 저장
            if (k == 1) homes.push_back({i, j});
            if (k == 2) chickens.push_back({i, j});
        }
    }

    // chickens에서 폐업되지 않은 치킨집 M개의 경우의 수를 구한다.
    combi(-1, temp);

    // 반복문을 통해 치킨 거리를 구한다.
    for (auto temp : temps) { // ex) [1,2]
        pair<int, int> c;
        int sum = 0;
        int dist;
        for (auto h : homes) {
            int home = INF;
            for (auto elem : temp) {
                c = chickens[elem];
                dist = abs(h.first - c.first) + abs(h.second - c.second);
                home = min(home, dist);
            }
            sum += home;
        }
        ret = min(ret, sum);
    }

    cout << ret << "\n";

    return 0;
}