[백준 BOJ] 15686번 - 치킨 배달 (C++)

정다은·2022년 3월 13일

cpp 백준

교공 알고리즘 스터디 26주차 삼성기출

15686번: 치킨 배달 | 문제 바로가기

문제풀이 (2022-03-08 TUE 💻)

🤔 사담

와.. 쉬울 줄 알고 고른 문제였는데 꽤나 골치 아팠다..
왜 때문인지 조합을 떠올리는 거 자체가 어려웠다..
생각해보니 순열 조합 활용하는 문제 거의 안 풀어본 것 같다

처음에는 BFS 활용해서 집마다 가장 가까운 치킨 집을 표시하고..
뭐 이런식으로 구현하듯이 풀려고 했는데
뭔가 아닌 것 같은 느낌이 들어서 찾아보니 시간초과를 내는 코드임을 알 수 있었다 환장 🤷‍♀️

⭐ 풀이의 핵심

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

여기서 조합을 써야겠다는 느낌이 빡- 왔다면 코드 짜는 거 자체는 어렵지 않다
나는 갠적으로 조합 떠올리기까지 시간이 오래걸려서 힘들었다..
조합을 떠올린 후에는 아래와 같은 순서로 답을 구하면 된다

조합으로 M개의 치킨집을 뽑는다
각 집에서 M개의 치킨집까지의 거리 중 최솟값들을 구하여 더한다
위의 과정을 반복하며 가장 최소의 거리 합이 나오는 조합의 거리 값을 구한다

조합 제대로 익히고 넘어가자! 라는 생각으로
① DFS ② next_permutation 활용하는 두 가지 방법으로 구현해보았다

DFS는
중복이 없도록 탐색 시작 지점?을 알려주는 index와
선택한 개수를 알려주는 count를 활용하며
재귀 호출 전/후에 visited 값을 true/false로 바꿔주며 백트래킹이 가능하도록 한다

C++ 같은 경우는 algorithm 라이브러리에 있는 next_permutation 함수를 활용하면
보다 쉽게 조합을 구할 수 있다
다만 순열과 달리 조합은 순서가 상관없이 원소를 뽑는 것이기 때문에
cf) {1,2,3,4,5} 중에서 {1,2,3} 과 {3,2,1} 은 동일한 조합으로 여겨짐
선택하려는 숫자들이 들어있는 원본 벡터가 아니라
새로운 벡터에 N개의 원소 중 선택하려는 원소 개수 k만큼 1을, N-k만큼 0을 push하고
next_permutaion을 돌린 후 값이 1인 인덱스에 해당하는 값들만 원본 벡터에서 선택한다

🔽 DFS를 활용한 코드 (C++)

// Solution #1) dfs 활용

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX_INT 2147483647
struct House {
    int r, c;
};
struct Chicken {
    int r, c;
    bool visited;
};
int N, M;
int minCityDistance = MAX_INT; // 도시의 치킨 거리의 최솟값
vector<House> house;
vector<Chicken> chicken;

void calculateDistance() {
    // 각 집에 대해 선택된 M개의 치킨집과의 거리 중 최솟값 구하기
    // 이를 다 더하여 도시의 치킨 거리 구하고 현재의 최솟값 보다 작을 경우 최솟값 업데이트
    int cityDistance = 0;
    for (int i=0; i<house.size(); i++) {
        int minHouseDistance = MAX_INT;
        for (int j=0; j<chicken.size(); j++) {
            if (chicken[j].visited) {
                int houseDistance = abs(house[i].r - chicken[j].r) + abs(house[i].c - chicken[j].c);
                if (houseDistance < minHouseDistance) {
                    minHouseDistance = houseDistance;
                }
            }
        }
        cityDistance += minHouseDistance;
    }
    if (cityDistance < minCityDistance) {
        minCityDistance = cityDistance;
    }
}

void selectChicken(int index, int count) {
    // dfs + 조합
    // 폐업시키지 않을 치킨집 최대 M개 고르기
    if (count == M) {
        calculateDistance();
    }
    for (int i=index; i<chicken.size(); i++) {
        if (!chicken[i].visited) {
            chicken[i].visited = true;
            selectChicken(i, count + 1);
            chicken[i].visited = false;
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);

    int flag;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d", &flag);
            if (flag == 1) { house.push_back({i, j}); }
            else if (flag == 2) { chicken.push_back({i, j, false}); }
        }
    }

    selectChicken(0, 0);
    printf("%d", minCityDistance);

    return 0;
}

🔽 next_permutation을 활용한 코드 (C++)

// Solution #2) next_permutation 활용

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

#define MAX_INT 2147483647
int N, M;
int minCityDistance = MAX_INT;
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
vector<int> selected;

void calculateDistance() {
    int cityDistance = 0;
    for (int i=0; i<house.size(); i++) {
        int minHouseDistance = MAX_INT;
        for (int j=0; j<chicken.size(); j++) {
            if (selected[j] == 1) {
                int houseDistance = abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second);
                if (houseDistance < minHouseDistance) {
                    minHouseDistance = houseDistance;
                }
            }
        }
        cityDistance += minHouseDistance;
    }
    if (cityDistance < minCityDistance) {
        minCityDistance = cityDistance;
    }
}

void selectChicken() {
    for (int i=0; i<chicken.size()-M; i++) { selected.push_back(0); }
    for (int i=0; i<M; i++) { selected.push_back(1); }
    do {
        calculateDistance();
    } while(next_permutation(selected.begin(), selected.end()));
}

int main() {
    scanf("%d %d", &N, &M);

    int flag;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d", &flag);
            if (flag == 1) { house.push_back({i, j}); }
            else if (flag == 2) { chicken.push_back({i, j}); }
        }
    }

    selectChicken();
    printf("%d", minCityDistance);

    return 0;
}