[백준 - 15686] - 치킨 배달(구현) C++

문제

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

접근방법

문제 풀이 과정은 다음과 같다.

1. 치킨집 m개를 선정한다.('조합'을 이용해서)

2. 각 집마다 치킨 거리를 계산한 후 모두 더한다.

3. 그 중 가장 작은 값을 고른다.

 

문제 자체는 크게 어렵지 않아보였다. 시간이 관건이었다.

 

집의 좌표와 치킨집의 좌표를 각각 따로 vector에 저장해뒀다.

이 좌표들을 이용해서 구하면 graph 전체를 누비지 않아도 되서 시간이 절약된다.

또 치킨집 m개의 '조합'을 구할 수 있어야하는데, 이 방법을 사용해야 조합을 구하기 쉽다.

 

find_chicken함수는 도시 거리를 리턴한다.

여기 인자로 depth와 start를 줬는데, depth는 m개의 치킨 집을 구하기 위해서고, start는 순열이 아니라 조합을 구현하기 위해서다.

 

조합을 구현하기 위해서는 for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) 와 같이 중첩을 만들어야한다. j가 i+1부터 탐색을 시작해야 순열이 아닌 조합을 구현할 수 있기 때문에, 이를 재귀함수에서 구현하기 위해 start라는 변수를 인자로 전달한 것이다.

 

ms는 vector로 선언했지만, 스택의 역할을 한다. 스택을 사용해야 치킨집을 넣었다 뺐다하기 편하다. find_chicken함수는 dfs를 구현한 것이라고 보면 된다.

코드

#include <iostream>
#include <cmath> //for abs() function
#include <vector>
using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 
#define MAX 987654321
#define FASTER ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int n, m;
int graph[50][50];
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
vector<pair<int, int>> ms;

//도시의 치킨 거리 리턴
int find_chicken(int depth, int start) {
    int ret = MAX;
    //base case
    if (depth == 0) {
        //각 house마다 치킨거리를 계산.
        //현재 ms에 담긴 치킨 집이 전부라고 했을 때,
        //도시의 치킨 거리
        int dist = 0;
        for (auto h : house) {
            int temp = MAX;
            for (auto m : ms) {
                temp = min(temp, abs(h.first - m.first) + abs(h.second - m.second));
            }
            dist += temp;
        }
        return dist;
    }

    //m의 수 만큼 치킨 집을 ms에 저장.
    for (int i=start;i<chicken.size();i++) {
        ms.push_back(chicken[i]);
        ret = min(ret, find_chicken(depth-1, i + 1));     
        ms.pop_back();
    }
    return ret;
}

int main() {
    FASTER
    int ret = 0;
    cin >> n >> m;
    FOR(i, n) FOR(j, n) {
        cin >> graph[i][j];
        if (graph[i][j] == 1) house.push_back({i, j});
        if (graph[i][j] == 2) chicken.push_back({i, j});
    }
    ret = find_chicken(m, 0);
    cout << ret << '\n';
    return 0;
}

개선할 점

조합으로 구현해야하는데 순열로 구현해서 계속 시간 초과가 났다.

 

머리가 깨질 거 같았지만, 이런 과정도 다 피가되고 살이 되는 거 아니겠나.