[ 백준 ] 15686번 - 치킨 배달 (C++)

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

15686번: 치킨 배달

 

 

[ 문제풀이 ]

 

이 문제의 핵심은 조합을 뽑을 수 있는가 없는가입니다.

 

주어지는 치킨집들 중에서 맥시멈의 치킨집들을 조합으로 모두 뽑아내서 각 치킨집 중 가장 가까운 치킨집들의 거리를 각각 sum에 더해주고 그중 가장 작은 값을 ans에 경신시켜주어서 답을 내면 되는 아주 간단한 방식입니다.

 

처음에는 bfs를 통해서 가장 가까운 치킨집을 구하려고 했었지만 문제에도 나와있듯이 치킨집까지의 거리는 |r1-r2| + |c1-c2|이므로 조합으로 뽑은 모든 치킨집에 대입시켜 가장 가까운 치킨집을 선택하면 됩니다.

 

[ 소스 코드 ]

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct pos {            //각 좌표를 저장하기 위한 pos struct
    int y;
    int x;
};
 
int N, M;    
int arr[50][50];        //맵
vector<pos> chicken;    //치킨집의 좌표를 저장할 vector
pos box[13];            //조합을 저장할 배역
int sum;
int ans = 987654321;
 
void dfs(int level, int num)
{
    if (level == M)
    {
        sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    int min = 987654321;
                    for (int k = 0; k < M; k++) {
                        int y = box[k].y;        //조합으로 뽑은 치킨집의 좌표를 추출
                        int x = box[k].x;        //거리를 계산 후 dist에 저장
                        int dist = abs(y - i) + abs(x - j);
                        if (min > dist) {        //가장 작은 dist를 min에 저장
                            min = dist;
                        }
                    }
                    sum += min;            //sum에 min을 더함
                }
            }
        }
        if (ans > sum) {            //가장 작은 sum을 ans에 경신
            ans = sum;
        }
        return;
    }
 
    for (int i = num; i < chicken.size()-M+1+level; i++) {
        box[level] = chicken[i];
        dfs(level + 1, i + 1);
        box[level] = { 0,0 };
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];        
            if (arr[i][j] == 2) {    //치킨집들을 chicken vector에 push
                chicken.push_back({ i,j });
            }
        }
    }
 
    dfs(0, 0);
 
    cout << ans;
}