[BOJ 15686 // C++] 치킨 배달

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15686번 문제인 치킨 배달이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15686

15686번: 치킨 배달

이 문제는 숫자가 작아 나올 수 있는 경우의 수가 적으니 가능한 모든 경우를 탐색해서 풀었다.

 

1) 먼저 순열을 생성하는 recursion을 이용해 가능한 M개의 치킨집을 고르는 모든 경우의 수에 접근한다.

이 때, 각각의 치킨집을 pair의 형태로 좌표를 벡터에 저장해두면 순열을 생성하기 편해진다.

2) 각 집에서 현재 순열에 저장된 치킨집과의 거리중 최솟값들을 합한다. 이것이 현재 치킨집 순열에 대응되는 "도시의 치킨거리"이다.

3) 각 순열의 "도시의 치킨 거리" 중 최솟값을 구해 출력한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::vector;
using std::pair;
using std::cin;
using std::cout;

vector<pair<int, int>> chicken; // 모든 치킨집의 좌표를 저장한 벡터
vector<pair<int, int>> selectedchicken; // 치킨집의 순열을 저장할 벡터
vector<pair<int, int>> house; // 모든 집을 저장한 벡터

int min = 1000000000;

int dist(pair<int, int> pair1, pair<int, int> pair2) {
    return abs(pair1.first - pair2.first) + abs(pair1.second - pair2.second);
}

void func(int M, int cnt) { // recursion으로 치킨집의 순열의 경우의 수를 탐색
    vector<pair<int, int>>::iterator iterchicken;
    vector<pair<int, int>>::iterator iterhouse;
    if (selectedchicken.size() == M) { // 순열의 크기가 M이 되면
        int totaldist = 0; // totaldist: 도시의 치킨거리
        for (iterhouse = house.begin();iterhouse != house.end();iterhouse++) {
            int disttemp = 1000000000; // disttemp: 각 집의 치킨거리
            for (iterchicken = selectedchicken.begin();iterchicken != selectedchicken.end();iterchicken++) {
                int distance = dist(*iterhouse, *iterchicken);
                if (distance < disttemp) disttemp = distance;
            }
            totaldist += disttemp;
            if (min < totaldist) break; // 최적화: 다른 집들의 "치킨 거리"를 안 더해도 이미 답을 넘은 경우 탈출
        }
        if (min > totaldist) min = totaldist;
    }
    else { // 치킨집의 순열을 채우는 과정
        for (iterchicken = chicken.begin() + cnt; iterchicken != chicken.end();iterchicken++) {
            cnt++;
            selectedchicken.push_back(*iterchicken);
            func(M, cnt);
            selectedchicken.pop_back();
        }
    }
}


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

    int N, M;
    cin >> N >> M;
    int x;
    int k = 0;
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            cin >> x;
            if (x == 1) house.push_back({ i,j });
            else if (x == 2) {
                chicken.push_back({ i,j });
                k++;
            }
        }
    }
    func(M, 0);

    cout << min;

    return 0;
}