백준 15686 C++

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

15686번: 치킨 배달

 

문제 정리

주어진 도시 정보에서 M개의 치킨집만 남기는데 치킨집과 집 사이의 총 거리가 가장 적게 되도록 M개를 골라서 도시의 치킨 거리의 최솟값을 구하면 됨! (각 집과 치킨집 사이의 거리의 총 합이 최소가 되는)

 

생각

브루트포스로 모든 M개를 골랐을 때마다 거리를 다 구해놓고 그 중 min을 구함!

근데 M개를 고르는 로직은 어떻게 하지? 모든 경우의 수를 구한다고 하면 13의 13제곱...????? 이게 바로 브루트포스...????

하... ㄹㅇ 머임

 

치킨집의 위치를 체크하고 남겨놓을 치킨집을 골라서 각각의 거리를 비교하면서 최소 값을 구한다!

고를 때는 조합을 이용한다

왜 조합일까...

확통 공부한지가 벌써 4년 전... 1학년 때 확통을 미친 남용교수한테 들어서 생각도 안났나보다...

수학이 알고리즘에서 많이 쓰이니까 수학적으로도 접근을 해보는 습관을 길러야겠다 ㅎ

 

다시 정리하는 순열과 조합

순열 : 뽑는 순서에 따라 달라지면 순열

조합 : 순서를 바꿔도 결과가 같으면 조합

 

조합을 stl로 구현해도 되고 재귀로 구현해도 된다! 재귀로 구현하는 것은 이 분의 글을 참고하였다

https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

 

 

그니까 DFS에서 bool로 체크를 해서 다시 안쓰는 과정 + 재귀로 푸는 게 조합의 개념이 들어간 건가???

아 넘 헷갈려

 

재귀로 DFS(깊이 우선 탐색)을 구현해서 푸는 과정

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int N, M;
bool check[13];
vector<pair<int, int>> House;
vector<pair<int, int>> Chicken;
vector<pair<int, int>> Pick;
int Min = 987654321; // INF로 해도 돼용

void getChicken(int x, int cnt) {
    if (cnt == M) {
        int res = 0;
        for (int i = 0; i < House.size(); i++) {
            int min_dist = 987654321;
            for (int j = 0; j < Pick.size(); j++) {
                min_dist = min(min_dist, abs(House[i].first - Pick[j].first) + abs(House[i].second - Pick[j].second));
            }
            res += min_dist;
        }
        Min = min(Min, res);
        return;
    }
    for (int i = x; i < Chicken.size(); i++) {
        if (check[i] == true)
            continue;
        check[i] = true;
        Pick.push_back(Chicken[i]);
        getChicken(i, cnt + 1);
        check[i] = false;
        Pick.pop_back();
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int n;
            cin >> n;
            if (n == 1)
                House.push_back({i, j});
            else if (n == 2)
                Chicken.push_back({i, j});
        }
    }
    getChicken(0, 0);
    cout << Min;
}

 

void getChicken(int x, int cnt)

DFS를 이용하여 M개의 치킨집을 선택하는 함수를 정의한다. 

현재 인덱스 x와 선택된 치킨집의 개수 cnt를 매개변수로 받는다.

// 치킨집 조합 구하기
void getChicken(int x, int cnt) {
    if (cnt == M) {
    // M개의 치킨집을 선택한 경우
    // 각 집에 대해 가장 가까운 치킨집까지의 거리를 계산하여 최소 치킨 거리를 갱신
        int res = 0;
        for (int i = 0; i < House.size(); i++) {
            int min_dist = 987654321;
            for (int j = 0; j < Pick.size(); j++) {
                min_dist = min(min_dist, abs(House[i].first - Pick[j].first) + abs(House[i].second - Pick[j].second));
            }
            res += min_dist;
        }
        Min = min(Min, res);
        return;
    }
    ...
}

 

각 집에서 선택된 치킨집까지의 거리를 계산하고 거리의 합을 구하는 과정

House[i]는 현재 탐색 중인 집의 좌표를 나타내고 Pick[j]는 선택된 치킨집 중 하나의 좌표를 나타낸다.

abs(House[i].first - Pick[j].first)

 

이걸로 집의 x좌표와 치킨집의 x좌표 사이의 거리를 구한다.

abs(House[i].second - Pick[j].second)

이걸로 집의 y좌표와 치킨집의 y좌표 사이의 거리를 구한다.

abs(House[i].first - Pick[j].first) + abs(House[i].second - Pick[j].second)

이 두 거리를 합산하여 치킨집과 집 사이의 거리를 구한다. => 이게 바로 맨해튼 거리!!!

min_dist = min(min_dist, abs(House[i].first - Pick[j].first) + abs(House[i].second - Pick[j].second));

min_dist에는 이전 집까지의 거리 중에서 가장 작은 값을 저장한다.

res += min_dist;

res에는 모든 집에 대해 가장 가까운 치킨집과의 거리의 합을 누적하여 저장한다.

Min = min(Min, res);

 

현재까지 구한 치킨집의 조합 중에서 가장 작은 거리의 합을 저장한다.

 

재귀로 DFS 구현

void getChicken(int x, int cnt) {
    ...
    // 그렇지 않은 경우
    // 현재 인덱스부터 시작하여 치킨집을 선택하거나 선택하지 않고 다음 치킨집을 탐색
    for (int i = x; i < Chicken.size(); i++) {
        if (check[i] == true)
            continue;
        check[i] = true;
        Pick.push_back(Chicken[i]);
        getChicken(i, cnt + 1);
        check[i] = false;
        Pick.pop_back();
    }
}

bool 배열을 사용해 치킨집을 선택했는지 여부를 판단한다.

 - true인 경우 : 그냥 넘어감

 - false인 경우 : 이 치킨집을 선택하고 (check[i] = true) Pick 벡터에 해당 치킨집을 추가한다!

선택된 치킨집의 개수가 M개가 되면 재귀호출을 통해 거리 계산!

재귀호출이 끝나면 check[i]를 다시 false로 바꿔준 후 Pick 벡터에서 없애준다!

 

드디어 벡터를 써봤다

앞으로 벡터 쓰는 습관 + 함수 따로 쓰는 습관을 가져야 겠다

그냥 그게 나도 편할 듯

 

참고한 글 

https://nim-code.tistory.com/286

(c++)백준 15686번: 치킨 배달