[BOJ] 15686 : 치킨 배달

15686 : 치킨 배달

풀이

브루트포스

그냥 조합 짜서 bfs로 탐색해서 푸는 간단한 문제인줄 알았다.

그런데 경우의수를 구해보면 조합짜는게 2^13이고 bfs로 최대로나오면 맵크기인 50x50에다가 최대집의수 100을 곱하면

대략 25억이 나온다 맙소사.

그렇게 시간초과를 내고 곰곰이 생각해보니까 bfs를 굳이 안돌려되더라. (이부분 때문에 글을 썼다)

치킨집의 수가 압도적으로 적으므로 모든 집에서 모든 치킨집으로 가는 최소거리만 계산해주면 된다.

2^13 x 100 x 13 이 되버려서 대략 1300만으로 줄어든다. (50x50 -> 13)

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
int arr[51][51];
vector<pair<int, int>> vp;
vector<pair<int, int>> house;
int c[14];
int chikens = 0;
int ans=987654321;

void go(int idx, int cnt, int max) {
    if (idx>max) {
        return;
    }
    if (cnt == m) {
        int sum = 0;
        //각집에서 치킨집(c[j]!=0)들까지 거리를 계산 후 최소를 sum에 더한다 
        for (int i = 0; i < house.size(); i++) {
            int x = house[i].first;
            int y = house[i].second;
            int tmp = 987654321;
            for (int j = 0; j < max; j++) {
                if (c[j] != 0) {
                    int dist = abs(vp[j].first - x) + abs(vp[j].second - y);
                    if (dist < tmp)
                        tmp = dist;
                }
            }
            sum += tmp;
        }

        //정답보다 작으면 갱신
        if (sum < ans)
            ans = sum;
        return;
    }

    c[idx] = 1;
    go(idx + 1, cnt + 1, max);
    c[idx] = 0;
    go(idx + 1, cnt, max);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 2) {
                vp.push_back({i,j});
            }
            else if (arr[i][j] == 1) {
                house.push_back({i,j});
            }
        }
    }
    chikens = vp.size();
    go(0,0,chikens);
    cout << ans;
    return 0;
}

Written on April 10, 2019