[삼성SW테스트] 백준 15686번 - 치킨 배달

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

15686번: 치킨 배달

삼성 SW 역량테스트 기출 문제 '치킨 배달' 문제다.

단순 브루트포스 시뮬레이션으로 풀 수 있었던 문제다.

 

유의해야했던 점은 '최대 M개' 치킨집을 남기고 나머지는 폐점하는 것이어서 1개부터 M개까지 치킨집을 골라야 했다는 것이었다. 즉, 1개만 남겼을 때부터 해서 M개 모두 남기는 것 각각 next_permutation으로 풀어줘야 했다. 이를 위해 flag 벡터를 사용했는데, 다음 케이스(몇 개 남기는가에 대한)로 넘어갈 때 벡터를 다시 0으로 초기화 하고 해당 케이스의 치킨 집 개수만큼 다시 1을 넣어준뒤 소팅해서 next_permutation으로 해당 케이스의 최소 '도시의 치킨 거리'를 구하고, 이를 다시 global 최소 '도시의 치킨 거리'와 비교해 답을 갱신해주는 것이 필요했다.

 

아래는 내가 푼 c++ 소스코드이다. 실행시간은 16ms (제한시간 1s).

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
#define maxlen 51
using namespace std;
int N, M;
int Map[maxlen][maxlen];
vector<pair<int, int> > house, chicken_house;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int answer = INF;
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            cin >> Map[i][j];
            if (Map[i][j] == 1)
                house.push_back(make_pair(i, j));
            else if (Map[i][j] == 2)
                chicken_house.push_back(make_pair(i, j));
        }
    }
    vector<int> flag(chicken_house.size(), 0);
    for (int i = 1; i <= M; i++){
        for (int k = 0; k < i; k++)
            flag[k] = 1;
        // M개 만큼 1로 표시.
        sort(flag.begin(), flag.end());
        do{
            int Sum = 0;
            for (int z = 0; z < house.size(); z++){
                int cur_house_row = house[z].first;
                int cur_house_col = house[z].second;
                int cur_house_dist = INF;
                for (int j = 0; j < chicken_house.size(); j++){
                    if (flag[j]){
                        int chick_row = chicken_house[j].first, chick_col = chicken_house[j].second;
                        int cur_house_cur_chicken_dist = abs(cur_house_row - chick_row) + abs(cur_house_col - chick_col);
                        cur_house_dist = min(cur_house_dist, cur_house_cur_chicken_dist);
                    }
                }
                Sum += cur_house_dist;
            }
            // 도시의 치킨 거리 sum 구함.
            answer = min(answer, Sum);
        } while (next_permutation(flag.begin(), flag.end()));
        for (int s = 0; s < chicken_house.size(); s++)
            flag[s] = 0;
    }
    cout << answer << '\n';
    return 0;
}