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

[문제보기]

 15686. 치킨 배달

15686번: 치킨 배달

 

[풀이과정]

이 문제를 보고 완전 탐색을 사용해서 문제를 풀어야겠다고 생각했다. 재귀를 사용하여 치킨집을 M개를 골라서 

집이랑의 거리를 하나씩 측정하고 값을 갱신하는 부분에서 map을 사용하여 이중 for문으로 집 위치와 치킨집 위치를 

찾아 거리를 계산을 하면 시간이 많이 걸리기 때문에 처음 입력값을 받을 때 vector를 사용하여 집과 치킨집의 좌표를 

저장했다. 

 

dfs(int idx, int cnt) 함수를 진행하는데, idx변수를 입력받아 idx부터 for문을 진행해준다. 이때 check[] 라는 

1차원 배열을 사용하여, 치킨집을 골랐다면 true, 없앤다면 false로 입력을 해주면서 재귀를 진행해준다. 

재귀를 진행하면서 cnt는 치킨집을  몇 개 골랐는지를 의미하는 변수이므로 cnt가 n개가 되면 치킨집과 집과의

거리를 계산하는 get_dir() 함수를 진행해준다. 

 

get_dir()은 집과 치킨집의 거리를 계산해주는 함수인데, main에서 vector로 저장해준 집과 치킨집의 좌표를 사용하여

거리를 계산해준다. 이 부분에서 집과 계산을 하는 치킨집을 고르는 부분에서 check[] 변수를 사용하여 치킨집을 

골라준다.

[소스코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
int n, m, del;
int ans = 987654321;
int map[51][51] = {0};
bool check[13];
vector<pair<int, int>> house;
vector<pair<int, int>> chicken;

int get_dir(){
    int result = 0;
    for(int i=0; i<house.size(); i++){
        int sum = 987654321;
        for(int j=0; j<chicken.size(); j++){
            if(check[j]){
                sum = min(sum, abs(house[i].first - chicken[j].first) + abs(house[i].second - chicken[j].second));
            }
        }
        result += sum;
    }

    return result;
}

void dfs(int idx, int cnt){
    if(cnt == m){
        ans = min(ans, get_dir());
        return;
    }

    for(int i=idx; i<chicken.size(); i++){
        if(check[i] == true)
            continue;

        check[i] = true;
        dfs(i, cnt+1);
        check[i] = false;
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    cin >> n >> m;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> map[i][j];
            if(map[i][j] == 1){
                house.push_back({i,j});
            }
            else if(map[i][j] == 2){
                chicken.push_back({i,j});
            }
        }
    }

    dfs(0, 0);

    cout << ans ;
}

 

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

처음에는 dfs() 함수의 for문을 실행하는 부분에서 재귀로 들어갈 때마다 0부터 다시 확인하는 코드로 짰었다. 그래서

제출했을 때, 시간초과가 떠서, 이 부분을 잡기 위해서 고민을 했고, dfs() 함수에 idx를 같이 넘겨서 for문을 연산할 때

0부터가 아닌 idx부터 연산을 진행하도록 하는 것이 시간을 줄일 수 있는 방법이라는 것을 깨달았다.

 

시간을 잡기 위해서 1시간은 족히 고민을 했었고, 도무지 생각이 안 나서 블로그를 참고했다ㅠㅠㅠㅠㅠ.

이 부분만 잡았으면 바로 pass 할 수 있었는데ㅠㅠ