백준[15686] 치킨 배달

삼성 SW역량테스트 문제이다.  *작년 이문제를 풀어 면접을 봤었다...*

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

DFS(조합)를 사용해서 가능한 치킨집을 선별하여 문제에서 요구하는 거리의 합이 가장 작은 결과값을 출력하는 문제이다.

치킨집과 배달할 집의 좌표를 저장하고 선별한 치킨집에 따라 가까운 집을 선별하여 최단거리로 갈 수 있는 조합을 계속 갱신하면 답을 얻을 수 있다.

next_permutation() 함수를 사용했지만, 일반 재귀 DFS로도 구현 가능하다.

#include<stdio.h>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>
#include<deque>
 
using namespace std;
 
int main()
{
    int n, m, arr[55][55] = { 0 }, visit[15] = { 0 },ans2 = 987654321;
    int x[110] = { 0 }, y[110] = { 0 }, x2[15] = { 0 },y2[15] = { 0 },k = 0, k2 = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 1) {
                x[k] = i;
                y[k] = j;
                k++;
            }
            if (arr[i][j] == 2) {
                x2[k2] = i;
                y2[k2] = j;
                k2++;
            }
        }
    }
    for (int i = k2-m; i < k2; i++) visit[i] = 1;
    //cout << k << " " << k2 << endl;
    do {
        //for (int i = 0; i < k2; i++) {
            //printf("%d ", visit[i]);
        //}
        //printf("\n");
        int kx[13] = { 0 }, ky[13] = { 0 },kk=0;
        int ans = 0;
        for (int i = 0; i < k2; i++) {
            if (visit[i] == 1) {
                kx[kk] = x2[i];
                ky[kk] = y2[i];
                kk++;
                //cout << kx[kk-1] << " " << ky[kk-1] << " " << kk << endl;
            }
        }
        for (int i = 0; i < k; i++) {
            int ss = 0,dis = 987654321;
            for (int j = 0; j < kk; j++) {
                ss = abs(x[i] - kx[j]) + abs(y[i] - ky[j]);
                dis = min(dis, ss);
                //cout << ss << " " << dis << endl;
            }
            //printf("\n");
            ans = ans + dis;
            
        }
        ans2 = min(ans, ans2);
        //return 0;
 
    } while (next_permutation(visit, visit + k2));
    cout << ans2;
    return 0;
}