[백준]치킨배달

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

15686번: 치킨 배달

 

20분컷문제였다... 흐뭇.. 바로직전에 풀었던 연구소3과 매우 유사했기 때문이다. 심지어 더 쉬웠다.

먼저 치킨집들중 M개를 선택하는것이 똑같았다. 그리고 최소거리를 bfs로 구하는것도 똑같았다.

특별한 예외사항도 없었기 때문에 쉬웠던거 같다.

약간의 핵심이라고 한다면, 집-->치킨집, 치킨집-->집 으로 거리를 구하는 방법이 있었을텐데

치킨집이 더 효율적일거 같아서 치킨집-->집을 선택하였다.

문제의 해결방안은 아래와 같다.

1.BFS최소거리

2.DFS를 통해 치킨집 선택

3.가정집들마다 최소의 거리를 구해서 그것들의 최소값 구해주기

 

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
/*1.BFS최소거리 2.브루트포스로 최소값구하기 3.DFS(쪼합)
치킨집 들중 M개를 dfs로 선택하고 그 치킨집들중에서 bfs로 탐색한 후, 1을 만나는 최소거리를 누적
2에서 출발 --> 최단거리 다 구해놓고 맵에서 1일때 축적
예외사항 : 없음
*/
 
struct C_house {
    int r, c;
    bool Chosen;
    C_house() {};
    C_house(int r, int c, bool Chosen) :r(r), c(c), Chosen(Chosen) {};
};
 
vector<C_house> v1;
queue<pair<int, int> >q1;
int N, M, ans = 1e9;
int map[51][51];
int isV[51][51];
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
 
int solve() {
    int SUM = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 1) SUM += isV[i][j];
        }
    }
    return SUM;
}
 
void bfs() {
    while (!q1.empty()) {
        int nr = q1.front().first, nc = q1.front().second;
        q1.pop();
 
        for (int i = 0; i < 4; i++) {
            int nnr = nr + dr[i], nnc = nc + dc[i];
            if (nnr < 0 || nnc < 0 || nnr >= N || nnc >= N) continue;
            if (isV[nnr][nnc] == -1) {
                q1.push(make_pair(nnr, nnc));
                isV[nnr][nnc] = isV[nr][nc] + 1;
            }
        }
    }
}
 
void dfs(int start, int len) {
    if (len == M) {
        memset(isV, -1, sizeof(isV)); //해줄때마다 초기화
        for (int i = 0; i < v1.size(); i++) {
            if (v1[i].Chosen == true) {
                q1.push(make_pair(v1[i].r, v1[i].c));
                isV[v1[i].r][v1[i].c]++;
            }
        }
        bfs();
        int a = solve();
        if (a <= ans) ans = a;
        return;
    }
 
    for (int i = start; i < v1.size(); i++) {
        if (v1[i].Chosen == false) {
            v1[i].Chosen = true;
            dfs(i, len + 1);
            v1[i].Chosen = false;
        }
    }
}
 
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) v1.push_back(C_house(i, j, false)); }
    }
 
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}