15686 : 치킨 배달 - 조합(Combination), 브루트포스, 백트래킹

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

15686번: 치킨 배달

문제요약

가장 효율적인 치킨 집의 개수와, 치킨 집까지의 최소 거리의 합

 

난이도

Gold 5

---

풀이 포인트

• 조합

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();
    }
    return;
}

• 브루트 포스 , 백트래킹
  • 치킨집을 조합하는 경우의 수 구한 뒤,
  • 모든 집에서부터 치킨집까지의 거리의 합을 구하고, (브루트포스)
  • 이 중 거리가 가장 최소가되는 치킨집의 조합을 알아내야함.

---

REVIEW

 

치킨집의 조합을 구하는 것이 문제의 포인트.

조합을 구하는 재귀함수를 구현하느라 시간을 다 썼다.

소스 코드 참고하지 않고 혼자 구현해보고 싶어서 어찌저찌 5개 중 3개 이하의 치킨 집의 조합을 구하는 코드까지는 구현했다.

 

{0,1,2}가 있다고 할 때 첫번째 요소를 뽑고 두번째요소를 뽑는다, 안뽑는다의 2가지 경우의 수,

그 다음 요소를 뽑는다, 안뽑는다의 또 2가지 경우의 수. 

 

이런 식으로 뻗어나간다고 할 때, 매개변수 인덱스, bool값을 활용해서 어찌저찌 구현했다.

소스코드를 확인해본 결과, 비슷한 로직인 거 같긴하다.

 

여기에, 이제 치킨집 거리를 구해야하는데 바보처럼 최단 거리 bfs를 구해야한다고 생각하고 엄청 복잡하게 짜고 있다가,

문제를 하루지나 다시 읽어보니 그저 좌표 간 가로 세로 길이 더해주는 것이어서 수정했는데 오답.

 

여튼 모범답안에서 자료구조 유연하게 쓴 것들과, 인덱스 접근하는 것들 공부해두기.

조합을 for문으로만 구현해봤는데, 재귀를 맨땅에 헤딩하듯 구현해봐서 그래도 실력은 는 것 같다..

---

CODE

#include <bits/stdc++.h>
using namespace std;

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

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();
    }
    return;
}

int main()
{
    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> home : _home)
        {
            int _min = 987654321;
            for (int ch : cList)
            {
                int _dist = abs(home.first - chicken[ch].first) + abs(home.second - chicken[ch].second);
                _min = min(_min, _dist);
            }
            ret += _min;
        }
        result = min(result, ret);
    }
    cout << result << "\n";
    return 0;
}

//내가 구현한 조합 코드

#include <bits/stdc++.h>
using namespace std;

int n, m,a[51][51],b[51][51];

vector<pair<int,int>> cPos;
vector<pair<int,int>> hPos;

int cnt;

void pick(int idx, bool bb){


    if(bb){
        b[cPos[idx].first][cPos[idx].second] = 2;
        cout << cnt + 1 << "번째 조합이고, " << idx << "번 요소는 선택되었다\n";
    }else{
        b[cPos[idx].first][cPos[idx].second] = 0;
        cout << cnt + 1 << "번째 조합이고, " << idx << "번 요소는 선택되지 않았다.\n";
    }

    if(idx == cPos.size()-1){
        cnt++;
        
        cout << cnt <<"번째 조합이고, 치킨집을 표시해보면\n";
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cout << b[i][j] << " ";
            }
            cout << '\n';
        }

        cout << "치킨집 리셋\n";
        b[cPos[idx].first][cPos[idx].second] = 0;

        return;

    }

    pick(idx+1, true);
    pick(idx+1,false);
}

int main(){
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n;j++){
            cin >> a[i][j];
            b[i][j] = a[i][j];

            if(a[i][j] == 1) hPos.push_back({i,j});
            if(a[i][j] == 2){cPos.push_back({i,j});
                b[i][j] = 0;
            }
        }
    }


    for(int i = 0; i< cPos.size(); i++){
        pick(i, true);

        cout << "치킨집 리셋\n";
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (b[i][j] == 2)
                    b[i][j] = 0;
            }
        }
    }
    
}