치킨 배달(백준 15686번)

문제

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

15686번: 치킨 배달

이 문제를 처음 봤을 때 그냥 간단한 브루트포스 문제인 줄 알고 풀었다가 시간초과가 계속 나와서 다른 블로그를 보고 서야 풀 수 있었다... 길이를 구하는 것을 처음에는 집,치킨집 좌표를 기억해서 구하는 식으로 했다가 시간초과가 나서 bfs로 했는데 런타임에러가 떠서 결국에는 블로그를 찾아서 풀었다.

알고리즘 설명

1. 집,치킨집의 좌표를 벡터에 저장한다.

2. visit 배열을 만들어서 치킨집을 M에 맞게 뽑는다.

3. 다 뽑았으면 각 집마다 치킨집의 최소거리를 구한 다음 현재 뽑은 치킨집의 치킨거리를 구해준다.

 

코드

 

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
int N,M,Min = 987654321;
int map[51][51];
bool visit[13];
vector<pair<int,int>> chicken;
vector<pair<int,int>> home;
int absolute_value(int a,int b){
    int result = a-b;
    if(result<0){result = result*-1;}
    return result;
}
void dfs(int idx,int cnt){
    if(cnt == M){
        int result = 0;
        for(int i = 0;i<home.size();i++){
            int dis = 987654321;
            for(int j = 0;j<chicken.size();j++){
                if(visit[j] == true){
                    int y = absolute_value(home[i].first,chicken[j].first);
                    int x = absolute_value(home[i].second,chicken[j].second);
                    dis = min(dis,y+x);
                }
            }
            result = result+dis;
        }
        Min = min(Min,result);
        return;
    }
    else{
        if(idx == chicken.size())
            return;
        visit[idx] = true;
        dfs(idx+1,cnt+1);
        visit[idx] = false;
        dfs(idx+1,cnt);
    }
}
int main(int argc, char* argv[]){
    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){
                home.push_back(make_pair(i,j));
            }
            else if(map[i][j] == 2){
                chicken.push_back(make_pair(i,j));
            }
        }
    }
    dfs(0,0);
    cout << Min;
}