백준 15686 치킨 배달

구현 문제를 풀어보자고 해서 잡은 문제이다.

2D 지도를 입력받고,  치킨 집 중 M개를 선택해 각 집에서 가장 가까운 치킨집 거리들의 합 최소값을 구하면 되는 문제이다.

구현 문제기도 하고, 맵 크기도 50 * 50 = 2500개 셀이라 크지 않아서 전체 탐색으로 구현했다.

 

처음 맵 입력을 받을 때, 집 위치와 치킨집 위치를 각 벡터에 저장한다.

탐색하는 공간은 전체 치킨집 중에서 어떤 특정한 치킨집들을 선택하는 경우를 비트마스킹으로 탐색했다. 전체 탐색 공간의 수는 2^치킨집의 수 이다. 하지만 이 경우 중에서 선택한 치킨집의 수가(1의 수가) M개인 경우만 사용한다.

각 경우에서는 집을 순회하면서 그 집에서 가장 가까운 치킨집의 거리를 더해나간다. 가장 가까운 치킨집 거리 역시 각 치킨집을 모두 돌면서 최소값을 찾았다. 치킨집의 수도 최대 13개 이므로 다 돌아도 경우의 수가 많지 않다.

 

결국 (거의)전체 탐색을 돌면서 거리의 최소값을 찾는 문제이다. 구현하고 첫트에 맞았습니다를 띄웠다. 아싸.

---

#include <iostream>
#include <cstring>
#include <vector>
#include <climits>

int check_1(int i)
{
    int ret = 0;
    while (i)
    {
        ret += (i & 1);
        i = i >> 1;
    }
    return (ret);
}

int get_dist(std::pair<int, int> p1, std::pair<int, int> p2)
{
    return (std::abs(p1.first - p2.first) + std::abs(p1.second - p2.second));
}

int main()
{
    int map[51][51];
    memset(map, 0, sizeof(map));
    int N, M;
    std::vector<std::pair<int, int>> chicken;
    std::vector<std::pair<int, int>> house;
    std::cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            std::cin >> map[i][j];
            if (map[i][j] == 1)
                house.push_back(std::make_pair(i,j));
            else if (map[i][j] == 2)
                chicken.push_back(std::make_pair(i, j));
        }
    }
    
    int min_dist = INT_MAX;
    for (int i = 0; i < (1 << (chicken.size())); i++)
    {
        int dist = 0;
        if (M != check_1(i))
            continue;
        for (int j = 0; j < house.size(); j++)
        {
            int chicken_dist = INT_MAX;
            for (int k = 0; k < chicken.size(); k++)
            {
                if (i & (1 << k))
                {
                    chicken_dist = std::min(get_dist(house[j], chicken[k]), chicken_dist);
                }
            }
            dist += chicken_dist;
        }
        min_dist = std::min(min_dist, dist);
    }
    std::cout << min_dist;
}

 

구현 문제는 쉬운걸 잡으면 확 쉬워지는 느낌이다. 조금 어려운 것을 한번 풀어봐야겠다. 휴. 화이팅

 

오늘도 평온한 하루가 되길. 슨민.