[백준 15686] 치킨 배달

문제 바로가기

15686번: 치킨 배달

 

조합 + BFS로 풀 수 있다

놓을 수 있는 치킨 집을 조합으로 계산하고 치킨집 <-> 각 집의 거리를 구하기 위해 BFS를 하면 된다.

조합으로 풀 수 있는 문제가 참 많구만 ~

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
//조합, bfs 함께 풀면 됨

int N, M;
int map[50][50];
int dist[50][50];
int pos[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int min_D = 100000;

vector<pair<int, int>> store;
queue<pair<int, int>> Q;

bool isIn(int x, int y)
{
    if (x >= 0 && x < N && y >= 0 && y < N)
        return true;
    return false;
}

int countChickenD()
{
    int d = 0;
    while (!Q.empty())
    {
        pair<int, int> curr = Q.front();
        Q.pop();

        if (map[curr.first][curr.second] == 1)
        {
            d += (dist[curr.first][curr.second]-1);
        }

        for (int i = 0; i < 4; i++)
        {
            int nx = curr.second + pos[i][1];
            int ny = curr.first + pos[i][0];

            if (isIn(nx, ny))
            {
                if (!(dist[ny][nx] > 0 && (dist[curr.first][curr.second] + 1)))
                {
                    dist[ny][nx] = dist[curr.first][curr.second] + 1;
                    Q.push({ ny, nx });
                }
            }
        }
    }

    return d;
}
void choose_store(int d, int fd, int prev)
{
    if (d == fd)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (map[i][j] == 2)
                {
                    Q.push({ i, j });
                    dist[i][j] = 1;
                }
            }
        }
        min_D = min(min_D, countChickenD());
        memset(dist, 0, sizeof(dist));

        return;
    }
    for (int i = prev; i < store.size(); i++)
    {
        int nx = store[i].second;
        int ny = store[i].first;
        map[ny][nx] = 2;
        choose_store(d + 1, fd, i + 1);
        map[ny][nx] = 0;
    }
}
int main() {

    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] == 2) {
                store.push_back({ i, j });
                map[i][j] = 0;
            }

        }
    }


    choose_store(0, M, 0); //현재 선택한 치킨집 수, 최종 치킨집 수, 확인한 마지막 치킨집 좌표

    cout << min_D << endl;

    return 0;
}