백준 // 15686// 치킨 거리 //완전 탐색 하기~

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

 

Fried chicken~~

 

1) nexxt_permutation 사용 :0초 나옴

#include <iostream>
#include <vector>
#include <algorithm> // next_permutation
using namespace std;

int n, m; // 도시 크기, 유지할 치킨집 개수
vector<pair<int, int>> PericanaChickenLocations;
vector<pair<int, int>> HouseLocations;
vector<int> combination; // 조합 선택을 위한 배열

// 특정 치킨집 조합으로 도시의 치킨 거리 계산
int ChickenDistance(const vector<pair<int, int>>& selectedChicken)
{
    int totalChickenDistance = 0;
    
    for (auto house : HouseLocations)
    {
        int hx = house.first, hy = house.second;
        int minDistance = 1e9; // 큰 값으로 초기화 (최소값 찾기 위해)

        // 선택된 치킨집만 비교하여 최소 거리 찾기
        for (auto chicken : selectedChicken)
        {
            int cx = chicken.first, cy = chicken.second;
            int distance = abs(hx - cx) + abs(hy - cy); // 맨해튼 거리 공식
            minDistance = min(minDistance, distance);
        }

        totalChickenDistance += minDistance; // 최소 치킨 거리 합산
    }
    
    return totalChickenDistance;
}

// 치킨집 조합을 생성하여 최소 치킨 거리 계산
int GetMinChickenDistance()
{
    int minChickenDistance = 1e9; // 초기값 크게 설정

    // 치킨집 개수만큼 조합 인덱스 만들기 (M개 선택)
    combination.assign(PericanaChickenLocations.size(), 0);
    fill(combination.end() - m, combination.end(), 1); // 마지막 M개만 1로 설정

    do {
        vector<pair<int, int>> selectedChicken; // 선택된 M개의 치킨집
        for (size_t i = 0; i < PericanaChickenLocations.size(); i++)
        {
            if (combination[i]) selectedChicken.push_back(PericanaChickenLocations[i]);
        }

        // 선택된 M개의 치킨집으로 치킨 거리 계산
        int currentDistance = ChickenDistance(selectedChicken);
        minChickenDistance = min(minChickenDistance, currentDistance);

    } while (next_permutation(combination.begin(), combination.end()));

    return minChickenDistance;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    vector<vector<int>> ChickenMap(n, vector<int>(n));

    // 지도 입력 받기
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> ChickenMap[i][j];

            if (ChickenMap[i][j] == 1)
            {
                HouseLocations.push_back({ i + 1, j + 1 }); // 1-based index
            }
            else if (ChickenMap[i][j] == 2)
            {
                PericanaChickenLocations.push_back({ i + 1, j + 1 }); // 1-based index
            }
        }
    }

    // 🚀 조합을 이용한 최소 치킨 거리 계산
    int totalChickenDistance = GetMinChickenDistance();
    cout << totalChickenDistance << endl;

    return 0;
}

---

🟢 1️⃣ 기본 개념: next_permutation이 하는 일

🔹 주어진 숫자 배열을 "사전 순(lexicographical order)"으로 다음 순서의 배열 바꿈
🔹 배열이 숫자 순서라면 가능한 다음 큰 조합을 만든다.
🔹 숫자가 가장 큰 경우(예: 1 1 1 0 0처럼 내림차순)는 처음으로 돌아간다.

---

🟡 2️⃣ 예제 1: 0 0 1 1 1에서 next_permutation의 변화!

우리가 조합을 만들기 위해 사용하는 배열은:

0 0 1 1 1

이 배열을 next_permutation()을 호출할 때마다 "다음 순서"의 배열이 만들어짐.

---

🔢 Step 1: 현재 배열 (0 0 1 1 1)

0 0 1 1 1

이제 next_permutation()을 호출하면 다음으로 더 큰 조합을 찾음

---

🔢 Step 2: next_permutation의 동작 원리

💡 다음 순열을 찾는 알고리즘은 다음 단계를 거친다.

1️⃣ 배열을 뒤에서부터 확인하면서, "오름차순이 시작되는 지점"을 찾는다.

• 즉, 앞 숫자가 더 작은 곳을 찾는다.
• 여기서는 0 0 **1 1 1**에서 0 1이 오름차순을 만들고 있다.
• 0 (index=1) 이 변화를 만들 수 있는 가장 작은 숫자야.

2️⃣ 그 위치의 숫자(0)를, 그보다 오른쪽에서 "가장 작은 더 큰 수"와 바꾼다.

• 오른쪽에서 1을 찾고, 0과 교환한다.
• 그래서 0 0 1 1 1 → 0 1 0 1 1로 바뀐다.

3️⃣ 그 이후의 숫자들을 "가장 작은 순서"로 정렬한다.

• 여기서는 이미 정렬된 상태라 바꿀 필요 없어!

➡ 결과:

0 1 0 1 1

---

📌 combination 배열이 selectedChicken에 영향을 주는 방식

combination 조합에 따라서 selectedChicken에 PericanaChickenLocations[i] 값이 저장

---

🔎 코드 분석!

combination.assign(PericanaChickenLocations.size(), 0);
fill(combination.end() - m, combination.end(), 1); // 마지막 M개만 1로 설정

do {
    vector<pair<int, int>> selectedChicken; // 선택된 치킨집
    for (size_t i = 0; i < PericanaChickenLocations.size(); i++) {
        if (combination[i]) selectedChicken.push_back(PericanaChickenLocations[i]);
    }
} while (next_permutation(combination.begin(), combination.end()));

이 코드에서 중요한 건 combination[i]의 값이 1이면, PericanaChickenLocations[i]가 selectedChicken에 추가된다는 점이야!

---

🟢 예제

🎯 가정: 치킨집 5개 (PericanaChickenLocations.size() = 5), 선택할 치킨집 3개 (m = 3)

이제 combination이 어떻게 변하는지 보자!

🔹 Step 1: 초기 상태 (next_permutation 호출 전)

combination = {0, 0, 1, 1, 1}  // 마지막 3개만 1 (즉, 3개의 치킨집 선택)

이제 for 문을 실행하면:

for (size_t i = 0; i < PericanaChickenLocations.size(); i++) 
{
    if (combination[i]) selectedChicken.push_back(PericanaChickenLocations[i]);
}

여기서 combination[i] == 1인 인덱스만 선택됨 → 예를 들어:

PericanaChickenLocations = {A, B, C, D, E}  // 5개의 치킨집이 있다고 하자
combination =          {0, 0, 1, 1, 1}  // D, E, C 선택됨
selectedChicken = {C, D, E}  // 선택된 치킨집!

---

🔹 Step 2: next_permutation 호출 후

이제 next_permutation()을 한 번 실행하면:

combination = {0, 1, 0, 1, 1}  // 새로운 조합!

이번에는 combination[i] == 1인 애들이 바뀌었으니까, selectedChicken도 바뀜:

PericanaChickenLocations = {A, B, C, D, E}
combination =          {0, 1, 0, 1, 1}  // B, D, E 선택됨
selectedChicken = {B, D, E}  // 새로운 조합!

---

🔹 Step 3: next_permutation을 계속 실행하면?

계속 실행할 때마다 combination이 변하면서 selectedChicken에 들어가는 값이 바뀐다!

호출 횟수 combination selectedChicken

1️⃣	0 0 1 1 1	{C, D, E}
2️⃣	0 1 0 1 1	{B, D, E}
3️⃣	0 1 1 0 1	{B, C, E}
4️⃣	0 1 1 1 0	{B, C, D}
5️⃣	1 0 0 1 1	{A, D, E}

---

✅ 결론

• combination 배열에서 1인 위치만 selectedChicken에 들어간다!
• next_permutation이 실행될 때마다 combination이 변하면서 selectedChicken 조합도 변한다.
• 이 방식 덕분에 모든 가능한 치킨집 조합을 빠르게 탐색할 수 있다! 🚀

 

 

 

 

2) combination 함수 생성 : 대략 4초 나옴

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

int n, m, a[54][54], result = 987654321;
vector<vector<int>> chickenList;
vector<pair<int, int>> home, chicken;

// ✅ 치킨집 조합 만들기 (DFS 활용)
void combi(int start, vector<int> v) 
{
    if (v.size() == m) 
    {
        chickenList.push_back(v);
        return;
    }
    for (int i = start + 1; i < chicken.size(); i++) 
    {
        v.push_back(i);
        combi(i, v);
        v.pop_back();
    }
}

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

    // ✅ 입력 받기
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            cin >> a[i][j];
            if (a[i][j] == 1) home.push_back({ i, j });   // 집 위치 저장
            if (a[i][j] == 2) chicken.push_back({ i, j }); // 치킨집 위치 저장
        }
    }

    // ✅ 모든 치킨집 조합 생성
    vector<int> v;
    combi(-1, v);

    // ✅ 각 조합마다 최소 치킨 거리 계산
    for (vector<int> cList : chickenList) 
    {
        int ret = 0;

        for (pair<int, int> h : home) 
        {
            int _min = 987654321;  // 최소 치킨 거리 초기화

            for (int ch : cList) 
            {
                int _dist = abs(h.first - chicken[ch].first) + abs(h.second - chicken[ch].second);
                _min = min(_min, _dist);
            }

            ret += _min;  // 선택된 치킨집 중 최소 거리 누적
        }

        result = min(result, ret);  // 최소 치킨 거리 업데이트
    }

    cout << result << '\n';  // ✅ 최종 결과 출력 (문제 형식에 맞춤)
    return 0;
}

 

 

두 코드의 실행 시간 차이가 발생하는 이유는 치킨집 조합을 생성하는 방식의 차이 때문

---

🔎 두 코드의 차이점 분석

1️⃣ 두 번째 코드: DFS를 이용한 조합 생성

void combi(int start, vector<int> v) 
{
    if (v.size() == m) 
    {
        chickenList.push_back(v);
        return;
    }
    for (int i = start + 1; i < chicken.size(); i++) 
    {
        v.push_back(i);
        combi(i, v);
        v.pop_back();
    }
}

• DFS(백트래킹)를 이용해 조합을 만들고, 가능한 모든 치킨집 조합을 chickenList에 저장한 후 나중에 거리 계산을 수행한다.
• 조합을 미리 다 만들어 저장하므로, 메모리 사용량이 증가하며 탐색이 비효율적
• 조합을 먼저 구하고 다시 반복문으로 거리를 계산하는 방식이라 시간이 오래 걸린다.

---

2️⃣ 첫 번째 코드: next_permutation을 이용한 조합 생성

combination.assign(PericanaChickenLocations.size(), 0);
fill(combination.end() - m, combination.end(), 1); // 마지막 M개만 1로 설정

do {
    vector<pair<int, int>> selectedChicken;
    for (size_t i = 0; i < PericanaChickenLocations.size(); i++) 
    {
        if (combination[i]) selectedChicken.push_back(PericanaChickenLocations[i]);
    }

    int currentDistance = ChickenDistance(selectedChicken);
    minChickenDistance = min(minChickenDistance, currentDistance);

} while (next_permutation(combination.begin(), combination.end()));

• next_permutation을 사용하여 순열(조합)을 직접 생성하며 바로 계산
• 불필요한 메모리 사용 없이 매 조합을 생성하자마자 거리 계산을 수행하여 속도가 빠르다.
• fill(combination.end() - m, combination.end(), 1); 이 부분을 활용해 O(M)만큼의 메모리만 사용하여 조합을 관리한다.

---

🏎️ 속도 차이가 발생하는 이유

요소 첫 번째 코드 (DFS) 두 번째 코드 (next_permutation)

조합 생성 방법	DFS로 모든 조합을 먼저 생성	next_permutation으로 바로 사용
조합 저장 방식	chickenList 벡터에 미리 저장	조합을 만들면서 바로 계산
메모리 사용량	chickenList에 모든 조합 저장 (메모리 낭비)	조합을 저장하지 않고 바로 처리
시간 복잡도	O(KCm)×O(NH)O(KCm) \times O(NH)	O(KCm×NH)O(KCm \times NH)
최적화 여부	조합을 따로 저장해서 비효율적	즉시 계산하여 빠름

🔹 조합의 개수 KCm

• 치킨집이 K=13K = 13개라면, m=6m = 6개를 선택하는 조합 수는 C(13,6)=1716C(13,6) = 1716개.
• DFS는 이 모든 조합을 chickenList에 저장한 후 계산해서 메모리 낭비 + 탐색 시간이 길어짐.
• next_permutation은 조합을 만들면서 바로 계산하여 메모리 절약 + 실행 속도 향상.

---

✅ 결론

• 첫 번째 코드(DFS)는 모든 조합을 먼저 저장하고 나중에 거리 계산을 수행하기 때문에 메모리 낭비가 많고, 전체 탐색 속도가 느려진다.
• 두 번째 코드(next_permutation)는 조합을 만들면서 바로 거리 계산을 수행하므로 메모리를 덜 사용하고 실행 속도가 빠르다.
• 🚀 두 번째 코드가 0초 내에 실행되는 이유는 조합을 저장하지 않고 즉시 처리하는 최적화 덕분!