[백준] 15686번: 치킨 배달 (C++ 풀이)

문제

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

 

풀이

도시에 있는 치킨집 중 폐업하지 않을 m개의 치킨집을 골라서 최소의 치킨거리를 찾아내야하는 문제이기 때문에

모든 경우의 수를 봐야하므로 완전탐색으로 풀었다.

 

1. 입력을 받을 때 치킨집(2)이면 모든 치킨집를 저장하는 스택 v에 좌표를 저장해두었다. (vector<pair<int, int>> v)

2. dfs를 통해 치킨집 조합을 만들어낸다. (vector<pair<int, int>> tmp)

3. (tmp.size()==m)이 될때 치킨거리를 계산한다.

4. 치킨거리는 tmp에 있는 치킨집을 기준으로 도시를 for문으로 돌면서 집(1)이 나오면 치킨거리를 계산하는 방식이다.

5. tmp에 있는 모든 치킨집을 돌았으면 도시의 치킨거리를 계산하여 정답을 담을 ans에 최소값을 갱신한다.

 

※ 수 없이 많이 틀린 이유 ※

ans를 최소값으로 갱신하기 위해 최대값으로 초기화해두었는데,

최대값을 너무 작은값으로 초기화해놓은것이 잘못이었다. (max_dst)

n의 최대값은 50이고, m의 최대값은 13이다. 

치킨거리는 최대 100이 될 수 있고, 치킨집은 최대 13이니까

ans의 최대값은 1300정도가 될 수 있을 것이다.

안전하게 아예 큰 값(123456789)로 해두었어도... 금방 풀었을텐데...ㅜㅜ

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
 
const int max_dst = 1300;
int n, m;
int s[51][51];    //도시의 정보
int d[51][51];    //치킨거리를 저장하는 배열
vector<pair<int, int>> v;    //모든 치킨집
vector<pair<int, int>> tmp;    //최대 m개의 치킨집
int ans = max_dst;
 
void init_d() {        //d배열 초기화
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            d[i][j] = max_dst;
}
 
void calc() {    
    //각 집의 치킨거리 계산
    for (int i = 0; i < tmp.size(); i++) {
        int cx = tmp[i].first;
        int cy = tmp[i].second;
 
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (s[j][k] == 1)
                    d[j][k] = min(d[j][k], abs(cx - j) + abs(cy - k));
            }
        }
    }
 
    //도시의 치킨거리 계산
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == 1)
                sum += d[i][j];
        }
    }
    ans = min(ans, sum);
}
 
void dfs(int idx) {        //m만큼의 치킨집을 고르는 경우들
    if (tmp.size() == m) {    //기저조건
        init_d();
        calc();
        return;
    }
 
    for (int i = idx; i < v.size(); i++) {
        tmp.push_back(make_pair(v[i].first, v[i].second));
        dfs(i + 1);
        tmp.pop_back();
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &s[i][j]);
            if (s[i][j] == 2)
                v.push_back(make_pair(i, j));
        }
    }
 
    dfs(0);
    printf("%d", ans);
 
    return 0;
}

 

https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/15686.cpp

결과