백준 15686번 치킨 배달

문제 링크입니다: https://www.acmicpc.net/problem/15686

오랜만에 브루트 포스(Brute Force) 문제였습니다.

문제에서 요구하는 점을 파악하는데 시간이 조금 걸렸는데 결국 모든 집에 대해 제일 가까운 치킨 집까지의 거리의 합을 출력하는 것이였습니다.

알고리즘은 아래와 같습니다.

1. 도시 정보를 입력 받을 때, 집은 house 치킨은 chicken 벡터에 좌표를 넣어줍니다.

2. 이후 DFS 함수를 호출하며 0번 치킨 집부터 (chicken.size() - 1)번 치킨 집까지 선택하거나 선택하지 않은 상태로 DFS 함수를 재귀 호출합니다.

3. 2번을 수행하는 도중 M개의 치킨 집이 선정되었다면 맨해튼 거리를 계산하여 문제에서 요구하는 결과를 계산하고 result를 업데이트해줍니다.

4. 2, 3번 과정이 마친다면 도시의 치킨 거리 최소값이 result에 저장되어있을 것입니다. 따라서, result를 출력해주면 됩니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 50;

const int INF = 987654321;

 

int N, M;

int result;

int graph[MAX][MAX];

vector<pair<int, int>> house, chicken;

bool visited[13];

 

//맨해튼 거리

int distance(pair<int, int> a, pair<int, int> b)

{

        return abs(a.first - b.first) + abs(a.second - b.second);

}

 

void DFS(int idx, int selected)

{

        //조건 만족

        if (selected == M)

        {

                 int tempResult = 0;

                 for (int i = 0; i < house.size(); i++)

                 {

                         int dist = INF;

                         for (int j = 0; j < chicken.size(); j++)

                                 if (visited[j])

                                          dist = min(dist, distance(house[i], chicken[j]));

                        

                         tempResult += dist;

                 }

                 result = min(result, tempResult);

                 return;

        }

 

        //기저 사례

        if (idx == chicken.size())

                 return;

 

        //프랜차이즈 선정

        visited[idx] = true;

        DFS(idx + 1, selected + 1);

        //프랜차이즈 선정 X

        visited[idx] = false;

        DFS(idx + 1, selected);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        for(int i=0; i<N; i++)

                 for (int j = 0; j < N; j++)

                 {

                         cin >> graph[i][j];

                         if (graph[i][j] == 1)

                                 house.push_back({ i, j });

                         else if (graph[i][j] == 2)

                                 chicken.push_back({ i, j });

                 }

 

        result = INF;

        DFS(0, 0);

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~