15686번

15686번 - 치킨 배달

삼성 상반기 기출문제로 알려져 있는 문제. 

오랜만에 PS를 다시 시작하니까 뭔가 감을 잃어버린 느낌...

처음에 문제가 꽤 복잡하다고 생각해서 문제를 여러번 읽어봤다.

어떤 걸 먼저 접근해서, 고정시키고 풀어야할지를 생각하면서 풀어봤다.

그러다가 치킨집을 선택할 수 있는 제한값이 낮기 때문에, 이를 이용해서 재귀함수를 구현하고, 완전탐색을 하였다.

치킨집을 최대 M개 선택할 수 있기 때문에, 1~M까지 치킨집을 모두 구해야한다. 기본적으로.

물론 최소 거리를 구하기 때문에, 가지치기를 통해서 충분히 전부하지 않고 구할 수 있을 것이라고 생각한다. (하지만 난 구현하지는 않았다.)

그리고 치킨집이 많을 수록 그 거리를 최소화 할 확률이 높기 때문에 main 함수에서 for문은 가장 큰 M부터 시작하기로 생각하였다.

다른 분들의 코드를 보고 생각하면서 위에 밑줄 친 부분이 필요없다는 사실을 깨달았다. 왜냐하면 만약 2개를 골라서 최솟값을 구했는데,

최대 5개를 고를 수 있다면 그 2개는 5개에 포함되기 때문에 자동으로 구해진다는 점이다. 따라서 최대 M개의 치킨집을 선택하기만 하면 된

다. 그리고 이로 인해서 시간을 좀 많이 단축할 수 있게 되었다.

이제 재귀함수에서는 치킨집을 선택한다 / 선택하지 않는다 로 나누어서 재귀함수를 구현했다.

selected 배열을 통해서 선택된 치킨집들의 인덱스 값을 저장시켜주었다.

그리고 치킨집 선택이 끝나면, 각 아파트와 모든 치킨집과의 거리를 구하면서 최솟값을 구하였다.

그리고 이 최솟값들을 모두 합해서 정답을 구하는 방식으로 문제를 풀 수 있었다.

<정답 코드 (수정 전)>

#include<iostream>
#include<vector>
using namespace std;
 
#define MAX 987654321
 
int n, m;
int ans = MAX;
int map[51][51];
int selected[14];
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
void dfs(int N, int k,int idx)
{
    //주어진 치킨 집 범위를 넘어갈 때
    if (k > chicken.size())
        return;
 
    //치킨집 선택이 끝났을 때.
    if (idx == N)
    {
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            //가정집 선택
            int hx = house[i].first;
            int hy = house[i].second;
            int minimum = MAX;
            for (int j = 0; j < idx; j++) {
                //모든 치킨집과의 거리 구하기
                int spot = selected[j];
                int cx = chicken[spot].first;
                int cy = chicken[spot].second;
                int val = abs(hx - cx) + abs(hy - cy);
 
                //최소 구하기
                if (val < minimum)
                    minimum = val;
 
            }
 
            //모든 집들의 최솟값의 합 구하기
            sum += minimum;
        }
 
 
        //정답 구하기
        if (sum < ans)
            ans = sum;
        
 
        return;
    }
 
    //치킨집 선택
    selected[idx] = k;
    dfs(N, k + 1, idx + 1);
 
    //치킨집 선택X
    selected[idx] = -1;
    dfs(N, k + 1, idx);
 
}
 
int main()
{
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2)        //치킨 집 표시
                chicken.push_back({ i,j });
 
            if (map[i][j] == 1)        //가정 집 표시
                house.push_back({ i,j });
        }
 
 
    //치킨집 고르기
 
    for (int i = m; i >= 1; i--)
        dfs(i, 0, 0);    
 
    
 
    cout << ans << endl;
 
    return 0;
}

<정답 코드(수정 후)>

#include<iostream>
#include<vector>
using namespace std;
 
#define MAX 987654321
 
int n, m;
int ans = MAX;
int map[51][51];
int selected[14];
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
void dfs(int N, int k, int idx)
{
    //주어진 치킨 집 범위를 넘어갈 때
    if (k > chicken.size())
        return;
 
    //치킨집 선택이 끝났을 때.
    if (idx == N)
    {
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            //가정집 선택
            int hx = house[i].first;
            int hy = house[i].second;
            int minimum = MAX;
            for (int j = 0; j < idx; j++) {
                //모든 치킨집과의 거리 구하기
                int spot = selected[j];
                int cx = chicken[spot].first;
                int cy = chicken[spot].second;
                int val = abs(hx - cx) + abs(hy - cy);
 
                //최소 구하기
                if (val < minimum)
                    minimum = val;
 
            }
 
            //모든 집들의 최솟값의 합 구하기
            sum += minimum;
        }
 
 
        //정답 구하기
        if (sum < ans)
            ans = sum;
 
 
        return;
    }
 
    //치킨집 선택
    selected[idx] = k;
    dfs(N, k + 1, idx + 1);
 
    //치킨집 선택X
    selected[idx] = -1;
    dfs(N, k + 1, idx);
 
}
 
int main()
{
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2)        //치킨 집 표시
                chicken.push_back({ i,j });
 
            if (map[i][j] == 1)        //가정 집 표시
                house.push_back({ i,j });
        }
 
 
    //치킨집 고르기
 
    dfs(m, 0, 0);
 
 
 
    cout << ans << endl;
 
    return 0;
}
 

<정답 코드 - 비트연산 사용>

#include<iostream>
#include<vector>
using namespace std;
#define INF 987654321
int N, M;
int map[51][51];
int ans = INF;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
void go(int k,int selected_num, int select)
{
 
    if (selected_num == M)
    {
        int total = 0;
        for (int i = 0; i < house.size(); i++)
        {
            int MIN = INF;
            for (int j = 0; j < chicken.size(); j++)
            {
                if (select & (1 << j))
                {
                    int sum = 0;
                    sum += abs(house[i].first - chicken[j].first);
                    sum += abs(house[i].second - chicken[j].second);
                    if (MIN > sum)
                        MIN = sum;
                }
            }
 
            total += MIN;
        }
 
 
        if (total < ans)
            ans = total;
 
 
        return;
    }
 
    if (k == chicken.size())
        return;
 
 
    go(k + 1 , selected_num + 1, select | (1 << k));
    go(k + 1, selected_num, select);
 
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2)
            {
                chicken.push_back({ i,j });
            }
            if (map[i][j] == 1)
            {
                house.push_back({ i,j });
            }
        }
    }
 
    go(0,0,0);
 
    cout << ans << endl;
 
    return 0;
}