백준 15686번 - 치킨 배달

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

위의 문제를 2가지 방법으로 풀었다.

첫 번째 방법은 DFS로 각각의 치킨집을 폐업할지 안할지를 확인한 후에 M개 만큼 열기로 했을 때 치킨 거리를 구하는 것이다.

두 번재 방법도 이와 동일한데, 순열 (next_permutation) 방식으로 구하는 것이다.

두 가지 모두 해결 방법은 동일하고 구현 방식만 조금 다르다.

먼저 집과 치킨집 각각의 좌표를 저장한다.

모든 좌표를 저장한 후에, 치킨 집의 개수 만큼 폐업 유무를 확인하는 배열을 만들어 M개 만큼 치킨집을 열기로 확인을 완료하면

브루투 포스 방식으로 각각의 집마다 열기로 한 치킨 집과의 치킨 거리를 구하면 된다.

주의할 점은 dfs 함수 부분에서 

치킨 집의 범위 보다 (두 번째 if문)

M개의 치킨집을 열었는지 먼저 확인해야 하는 것이다. (첫 번째 if문)

만약 마지막 치킨집을 열기로 하고 다음 dfs문을 타게 되면 M개가 열렸는데도 불구하고 치킨 거리를 확인하지 못하고 리턴하기 때문이다.

두 번째 방식은 위와 동일하며, next_permutation을 이용하여 모든 경우에서 치킨 거리를 구하면 된다.

#1

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
 
int N, M;
int ans = 0;
vector<pair<int, int>> house; //집 좌표
vector<pair<int, int>> chicken; //치킨집 좌표
vector<int> open; //치킨 집 폐업 유무
 
int house_cnt=0; //집 개수
int chicken_cnt=0; //치킨집 개수
 
//치킨 거리 구하기
void solve() {
    
    
    vector<int> dist(house_cnt,100); //치킨 거리
    for (int i = 0; i < house_cnt; i++) {
        
        int r1 = house[i].first;
        int c1 = house[i].second;
        for (int j = 0; j < chicken_cnt; j++) {
            if (open[j] == 0)
                continue;
            
            int r2 = chicken[j].first;
            int c2 = chicken[j].second;
            dist[i] = min(dist[i], abs(r1 - r2) + abs(c1 - c2));
        }
    }
    
    int sum = 0;
    for (int i = 0; i < house_cnt; i++)
        sum += dist[i];
    
    if (ans == 0) ans = sum;
    else ans = min(ans, sum);
    
}
 
void dfs(int pos, int cnt) {
    
    if (cnt == M) { //최소 M개 만큼 열었을 때
        solve();
        return;
    }
    
    if (pos == chicken_cnt) //확인해야 할 치킨 집 범위 확인
        return;
    
    open[pos]++;
    dfs(pos + 1, cnt + 1);
    
    open[pos]--; //폐업
    dfs(pos + 1, cnt);
    
}
 
int main() {
    
    cin >> N >> M;
    
    int city_info; //도시 정보
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &city_info);
            if (city_info == 1) {
                house.push_back(make_pair(i, j));
            }
            if (city_info == 2) {
                chicken.push_back(make_pair(i, j));
                open.push_back(0); //모두 폐업으로 초기화
            }
        }
    }
    
    house_cnt=(int)house.size();
    chicken_cnt=(int)chicken.size();
    
    
    dfs(0, 0);
    cout << ans << endl;
    
    return 0;
}
 

#2

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
 
int N, M;
int ans = 0;
vector<pair<int, int>> house; //집 좌표
vector<pair<int, int>> chicken; //치킨집 좌표
vector<int> open; //치킨 집 폐업 유무
 
int house_cnt=0; //집 개수
int chicken_cnt=0; //치킨집 개수
 
int main() {
    
    cin >> N >> M;
    
    int city_info; //도시 정보
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &city_info);
            if (city_info == 1) {
                house.push_back(make_pair(i, j));
            }
            if (city_info == 2) {
                chicken.push_back(make_pair(i, j));
                open.push_back(0); //모두 폐업으로 초기화
            }
        }
    }
    
    house_cnt=(int)house.size();
    chicken_cnt=(int)chicken.size();
    
    for(int i=0;i<M;i++)
        open[chicken_cnt-i-1]=1;
    
    do{
        vector<int> dist(house_cnt,100); //치킨 거리
        for (int i = 0; i < house_cnt; i++) {
            
            int r1 = house[i].first;
            int c1 = house[i].second;
            for (int j = 0; j < chicken_cnt; j++) {
                if (open[j] == 0)
                    continue;
                
                int r2 = chicken[j].first;
                int c2 = chicken[j].second;
                dist[i] = min(dist[i], abs(r1 - r2) + abs(c1 - c2));
            }
        }
        
        int sum = 0;
        for (int i = 0; i < house_cnt; i++)
            sum += dist[i];
        
        if (ans == 0) ans = sum;
        else ans = min(ans, sum);
        
    }while(next_permutation(open.begin(),open.end()));
    
    cout << ans << endl;
    
    return 0;
}