[Algorithm] 백준 15686 치킨 배달 - C++, DFS

15686번: 치킨 배달

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <algorithm>
using namespace std;

int n, m;
int result = INT32_MAX-1;
int city[51][51];
bool visit[14];
vector<pair<int, int>> houses;
vector<pair<int, int>> chicken;

int ChickenDistance(int houseIndex, int chickenIndex){
    pair<int, int> housePos = houses[houseIndex];
    pair<int, int> chickenPos = chicken[chickenIndex];

    return (abs(housePos.first - chickenPos.first) + abs(housePos.second - chickenPos.second));
}

void SearchChicken(int chickenIndex, int selectCount){
    if(selectCount == m){
        int curResult = 0;

        for(int i = 0; i < houses.size(); i++){
            int curDist = INT32_MAX;
            for(int j = 0; j < chicken.size(); j++){
                if(visit[j]){
                    curDist = min(curDist, ChickenDistance(i, j));
                }
            }
            curResult += curDist;
        }

        result = min(result, curResult);
    }

    if(chickenIndex == chicken.size())
        return;
    
    visit[chickenIndex] = true;
    SearchChicken(chickenIndex + 1, selectCount + 1);
    visit[chickenIndex] = false;
    SearchChicken(chickenIndex + 1, selectCount);
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> city[i][j];

            if(city[i][j] == 1){
                houses.push_back({i, j});
            }
            if(city[i][j] == 2){
                chicken.push_back({i, j});
            }
        }
    }

    SearchChicken(0, 0);
    cout << result << '\n';

}

---

 주어진 케이스가 크기 않아 그냥 생으로 다 탐색하는 방식입니다. DFS 라고 하기도 좀 그렇긴 하네요.

 일단 입력을 받으면서 치킨집과 집드의 좌표를 저장한 다음 이후 SearchChicken 함수를 돌려 치킨집을 살리는 모든 경우의 수를 탐색을 했습니다.

    if(chickenIndex == chicken.size())
        return;
    
    visit[chickenIndex] = true;
    SearchChicken(chickenIndex + 1, selectCount + 1);
    visit[chickenIndex] = false;
    SearchChicken(chickenIndex + 1, selectCount);

 이 부분만 잘 이해하면 될 듯한데 DFS 같은 재귀함수를 돌면서 '이번 방문한 치킨집을 선택하나 안하냐'로 이해하면 됩니다. 그리고 위 조건의 경우 인덱스 범위를 벗어나는 오류를 없애기 위해서 사용했습니다.