[삼성 기출 문제] 백준15686 치킨 배달

문제 링크

어떻게 풀까?

해당 문제는 전형적인 조합 문제입니다.

생각해봐야할 과제는 다음과 같습니다.

1. 맵에서 치킨집의 개수를 추출한 후에 비트 조합을 이용해서 m개의 치킨집만을 고른다.

2. 사람들이 사는 모든 집에서 현재 선택된 m개의 치킨 집 중에서 최소의 치킨집을 구한 후 더한다. (도시의 치킨 거리를 구한다.)

3. 최소의 도시의 치킨 거리 값을 출력한다.

만약, 비트 조합을 만드실줄 모른다면 여기를 참조하세요!

typedef struct Cod{ int r,c; } cod;
 
int cNum, pNum;
cod company[13];
cod people[100];
 
int getAllDist()
{
    int visit = (1 << m) - 1;
    int max = (1 << cNum);
    int minDist = 999999;
 
    while (visit < max)
    {
        int temp = visit | (visit - 1);
        int dist = 0;
        for (int i = 0; i < pNum; i++)
        {
            //i번쨰 사람의 치킨 거리를 구한다.
            dist += getDistance(i, visit);
        }
 
        //도시의 
        minDist = min(minDist, dist);
        visit = (temp + 1) | (((~temp & -~temp) - 1) >> (getZeros(visit) + 1));
    }
 
    return minDist;
}

이 부분이 바로 비트 조합을 이용해서 도시의 치킨 거리를 구하는 부분입니다.

그럼 이제, i번째 사람의 치킨 거리는 어떻게 구하면 될까요!?

현재 선택된 m개의 치킨 집들이 모두 비트로 표시되어 있습니다.

따라서, 이 정보들로 부터 i 번째 사람에서 현재 선택된 치킨 집들 까지의 모든 거리를 구할 수 있고,

이 중에서 최솟값이 바로 치킨 거리 입니다. 

만약, 비트 연산을 잘 모르신다면 여기를 참조하세요!

typedef struct Cod{ int r,c; } cod;
int cNum, pNum;
cod company[13];
cod people[100];

int getDistance(int num, int select)
{
    int index = 0;
    int dist = 99999;
    while (select)
    {
        if (select & 1)
        {
            int tempDistance;
            tempDistance = abs(people[num].r - company[index].r) + abs(people[num].c - company[index].c);
            dist = min(tempDistance, dist);
        }
        select >>= 1;
        index++;
    }
    return dist;
}
 

이번에는 이전에 써놓았던 글들을 통해서 쉽게 알고리즘을 풀 수 있는 문제였군요!

이제 이렇게 구한 도시의 치킨 거리를 출력해주면 끝납니다!

코드

#include<iostream>
#include<cstring>
 
using namespace std;
 
struct ChickenInfo
{
    int map[50][50];
    int n;
    int m;
    typedef struct Cod{ int r,c; } cod;
    int cNum, pNum;
    cod company[13];
    cod people[100];
 
    int abs(int i)
    {
        return i > 0 ? i : -i;
    }
 
    int min(int i1, int i2)
    {
        return i1 < i2 ? i1 : i2;
    }
 
    int getDistance(int num, int select)
    {
        int index = 0;
        int dist = 99999;
 
        while (select)
        {
            if (select & 1)
            {
                int tempDistance;
                tempDistance = abs(people[num].r - company[index].r) + abs(people[num].c - company[index].c);
                dist = min(tempDistance, dist);
            }
            select >>= 1;
            index++;
        }
 
        return dist;
    }
 
    int getZeros(int n)
    {
        int res = 0;
        while ((n & 1) == 0)
        {
            res++;
            n >>= 1;
        }
        return res;
    }
 
    int getAllDist()
    {
        int visit = (1 << m) - 1;
        int max = (1 << cNum);
        int minDist = 999999;
 
        while (visit < max)
        {
            int temp = visit | (visit - 1);
            int dist = 0;
            for (int i = 0; i < pNum; i++)
            {
                dist += getDistance(i, visit);
            }
 
            minDist = min(minDist, dist);
            visit = (temp + 1) | (((~temp & -~temp) - 1) >> (getZeros(visit) + 1));
        }
 
        return minDist;
    }
 
    void init()
    {
        memset(map, 0, sizeof(map));
        pNum = cNum = 0;
 
        cin >> n >> m;
 
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == 1)
                {
                    people[pNum].r = i;
                    people[pNum].c = j;
                    pNum++;
                }
                else if (map[i][j] == 2)
                {
                    company[cNum].r = i;
                    company[cNum].c = j;
                    cNum++;
                }
            }
        }
 
    }
}ChickInfo;
 
int main()
{
    ChickInfo.init();
    int res = ChickInfo.getAllDist();
    cout << res << '\n';
    return 0;
}

시간 복잡도

우선, 사람들의 수를 i라고 하겠습니다.

치킨 거리를 구하기 위해서는 i개의 집들이 m개의 치킨수를 모두 확인해야 합니다.

그리고, 조합은.. 최악의 경우도을 넘지 않기 때문에

시간 복잡도는  입니다.