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

[문제보기]

 

[해결과정]

 1. 좌표 구조체를 생성한다.

 2. 집 좌표 배열, 치킨 집 좌표 배열을 생성

  - ★집은 2N개이다. (가장 많이 틀리는 부분)

 

 3. 조합 (dfs) 수행

  - M개의 치킨 집 고르기

 

 4. 기저조건 상태라면, 집들을 돌며 치킨 집과의 거리를 구하고 가장 작은 거리를 sum에 더한다.

 5. sum 값과 ans를 비교하여 ans 갱신

 

[소스코드]

#include<iostream>
#include<memory.h>
#include<queue>
#include<vector>
#include<math.h>
using namespace std;
const int MAX = 52;
 
int arr[MAX][MAX];
int n, m;
 
// 구조체
struct Coor {
    int y;
    int x;
};
// 치킨집 카운트
int cCnt = 0;
Coor chi[15];
// 집 카운트
int hCnt = 0;
Coor home[102];
 
// 선택된 치킨 집
vector <int> v;
bool check[15];
 
int ans = 987987987;
 
// 조합
void dfs(int cnt, int a) {
    if (cnt == m) {
        // 기저조건
        int distance = 0;
 
        // 집들을 돌며 치킨집과의 거리를 구한다.
        for (int i = 0; i < hCnt; i++) {
            int hy = home[i].y;
            int hx = home[i].x;
 
            int minimum = 987987987;
 
            for (int j = 0; j < v.size(); j++) {
                int y = chi[v[j]].y;
                int x = chi[v[j]].x;
 
                int temp = abs(hy - y) + abs(hx - x);
                if (minimum > temp) minimum = temp;
            }
 
            distance += minimum;
        }
 
        if (ans > distance) ans = distance;
        
 
        return;
    }
 
    for (int i = a; i < cCnt; i++) {
        if (check[i] != 1) {
            check[i] = 1;
            v.push_back(i);
            dfs(cnt + 1, i);
            v.pop_back();
            check[i] = 0;
        }
    }
 
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    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) {
                chi[cCnt].y = i;
                chi[cCnt].x = j;
                cCnt++;
            }
            else if (arr[i][j] == 1) {
                home[hCnt].y = i;
                home[hCnt].x = j;
                hCnt++;
            }
        }
    }
 
    // 조합
    dfs(0,0);
 
    cout << ans << "\n";
 
 
 
    return 0;
}

 

 

[해결 과정 중 실수한 부분 / 잡담]

 삼성 기출문제다. 이 문제의 가장 틀리는 집의 개수... 나 역시 실수했다.. 쉽게 풀고 왜 답이 안나오지? 하다가, 자세히 보니 집의 개수가 달랐었다...

 

 삼성은 참 조합과 순열을 좋아한다............ 지금은 아니지만;

 

[관련 문제 혹은 비슷한 문제]

 삼성 기출