[BOJ] 치킨배달

[문제]

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

15686번: 치킨 배달

[풀이]

 

15686

맞았습니다!!

1996 KB

40 ms

C++14 / 수정

1557 B

1분 전

1) 재귀함수의 종료조건이 중요함. 최대 m개의 치킨집을 구하라고 해서 처음에는 m개보다 작거나 같다를 놓고 계속 실행했는데 2번 tc가 맞지 않았다. 

 

dfs(선택한 치킨집의 개수, 현재 치킨집 인덱스)

 

종료 조건은 선택한 치킨집의 개수가 m 개 이거나 현재 치킨집 인덱스가 치킨집 최대 개수와 같거나 넘어설때이다. 

 

2) 치킨집들의 조합을 구하고 calc() 함수를 실행해서 각 집에서 치킨집까지의 distance를 구한 후 최소값을 도출한다. sum에 모든 집과 치킨집과의 최소값을 누적합한다.

---

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
//풀이 38분
 
int n, m, map[51][51], ans = 987654321;
 
typedef pair<int, int> pp;
 
vector<pp> chicken, house;
 
bool visited[14];
 
int calcChickenDist();
 
void dfs(int cnt, int cur)
{
    if (cnt == m)
    {
        //최대 m개
        return;
    }
 
    if (cur >= chicken.size())
        return;
 
    for (int i = cur; i < chicken.size(); i++)
    {
        if (!visited[i] && cnt < m)
        {
            visited[i] = true;
            int res = calcChickenDist();
            ans = min(res, ans);
 
            dfs(cnt + 1, i);
            visited[i] = false;
        }
    }
}
int calcChickenDist()
{
    //모든 집과 치킨집 거리를 계산해서 최소값의 합
    int res = 0;
    for (int i = 0; i < house.size(); i++)
    {
        int minDist = 987654321;
        for (int j = 0; j < chicken.size(); j++)
        {
            if (visited[j])
            {
                int dist = (int)(abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second));
               
                minDist = min(dist, minDist);
            }
        }
        res += minDist;
    }
 
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(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] == 2)
            {
                chicken.push_back(pp(i, j));
            }
            else if (map[i][j] == 1)
            {
                house.push_back(pp(i, j));
            }
        }
    }
    //input
 
    dfs(0, 0); //m개의 치킨집을 고른다.
 
    cout << ans << '\n';
 
    return 0;
}