[BOJ / C++] 치킨 배달 (시뮬레이션)

문제링크: https://www.acmicpc.net/problem/15686

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> board(n, vector<int>(n));
    vector<pair<int, int>> home;
    vector<pair<int, int>> chicken;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 1) home.push_back({i, j});
            else if (board[i][j] == 2) chicken.push_back({i, j});
        }
    }

    vector<int> mask(chicken.size(), 1);
    for (int i = 0; i < m; i++) mask[i] = 0;

    int mn = 1e9;
    do {
        int totalDist = 0;

        for (int i = 0; i < home.size(); i++) {
            int hx, hy;
            tie(hx, hy) = home[i];
            
            int cDist = 1e9;
            for (int j = 0; j < mask.size(); j++) {
                if (mask[j] == 0) {
                    int cx, cy;
                    tie(cx, cy) = chicken[j];
                    cDist = min(cDist, abs(cx-hx) + abs(cy-hy));
                }
            }
            totalDist += cDist;
        }
        mn = min(mn, totalDist);

    } while (next_permutation(mask.begin(), mask.end()));
    
    cout << mn;
}

 

 

2. 분석

조합 문제이다. next_permutation을 이용해 조합문제는 쉽게 해결할 수 있다. mask 배열을 만드는 것이 핵심인데 배열을 1로 채우고, 배열의 맨 앞부터 선택한 치킨집 개수 m개 만큼 0으로 세팅해주고 next_permutation으로 순회하면된다. next_permutation을 할 때는 작은 수가 앞에 있는 채로 시작해야해서 약간 이상하지만 이렇게 하는게 편한 것 같다. 0일 때 해당 치킨집이 선택된 것이라고 생각한다! 모든 조합의 경우의 dist를 계산해서 완전 탐색하면 된다.

 

3. 시간복잡도

치킨 거리를 계산하는데 연산이 2n * m = 100 * 13이고, 각 치킨집의 조합 수가 13C6이므로 총 연산 횟수는 100 * 13 * 13C6 = 2,230,800 < 10^8으로 1초 이내 통과가 가능하다.