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

[문제보기]

 

[해결과정]

 1. (Y,X)를 저장할 수 있는 구조체를 생성

 2. 구조체를 담는 집 배열, 치킨 배열을 생성

 3. 각각의 배열에 카운트를 해주는 집 Cnt, 치킨 Cnt 변수 생성

 4. 입력 받기

 

 5. 조합(dfs)으로 치킨 집 m개 만큼 뽑기

 6. dfs 기저조건에서 모든 집에 대해, 뽑힌 치킨집과의 가장 짧은 거리를 저장

 

[소스코드]

#include<iostream>
#include<memory.h>
#include<math.h>
using namespace std;
const int MAX = 52;
 
int n, m;
int arr[MAX][MAX];
 
struct coor {
    int y;
    int x;
};
coor home[MAX*MAX];
int homeCnt;
coor chiken[15];
int chikenCnt;
 
bool check[15];
 
int ans = 987987987;
 
void dfs(int a, int cnt) {
    if (cnt >= m) {
        //기저조건
        int sum = 0;
        for (int i = 0; i < homeCnt; i++) {
            int homeMin = 987987987;
            for (int j = 0; j < chikenCnt; j++) {
                if (check[j] == 0) continue;
                int temp = abs(home[i].y - chiken[j].y) + abs(home[i].x - chiken[j].x);
                if (temp < homeMin) homeMin = temp;
            }
 
            if (homeMin == 987987987) continue;
            sum += homeMin;
        }
        if (sum < ans) ans = sum;
        return;
    }
    for (int i = a; i < chikenCnt; i++) {
        if (check[i] == 0) {
            check[i] = 1;
            dfs(i, cnt + 1);
            check[i] = 0;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                home[homeCnt] = { i,j };
                homeCnt++;
            }
            else if(arr[i][j]==2){
                chiken[chikenCnt] = { i,j };
                chikenCnt++;
            }
        }
    }
 
    dfs(0,0);
 
    cout << ans << "\n";
 
 
    return 0;
}
 
 

 

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

 삼성 역량테스트를 준비하며 처음 마주한 문제였다. 이번에는 sds pro특강에서 첫 문제로 마주했다. 처음에는 인강을 보며 지금도 잘 모르는 비트마스킹을 하며 풀었는데,.. 그건 생각조차 안나고;; 나만의 풀이법으로 풀었다.. 딴길로 샛지만.. 감격적인 순간이여서 나름 적어봤다.

 

 실수한 부분은 딱히 없었다. 조합과 약간의 구현이였던 것 같다.

 

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

 삼성 역량테스트