[C++] 백준 15686 치킨배달 - DFS도 재귀인데, 익숙하지 않다.

문제

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

리뷰

문제 유형: 구현, 백트래킹(브루트포스)

 

구현 문제에 백트래킹이 결합된 문제다. 백트래킹을 오랜만에 접해서 그런지, 쉬운 활용이었지만 생각해내기 어려웠다.

N개의 치킨 집 중 M개를 선정해야 하는데, 기준은 도시 치킨 거리를 최소화하는 M개이다.

먼저 N개 중 M개를 선택하기 위해서는 Recursive방식을 선택해야 한다(백트래킹). 재귀적으로 호출하며, end condtition으로 cnt == M 일때 원하는 계산을 수행하면 된다.

백트래킹의 단점은 stackoverflow를 발생시킬 수 있다는 것인데, 이를 방지하기 위해서는 몇 가지 장치가 필요하다.

A, B, C, D, E 중 3개를 선택하는 조합을 확인한다고 하면, 기준을 잡을 수 있다. A부터 시작해서 B, C, 그리고 , C, D, 이런 식으로 idx를 기준으로 나아갈 수 있다. B를 기준으로 시작할 때 A는 이전에 선택해봤던 조합이므로 고려하지 않아도 된다. 따라서, Recursive_Function(int idx, int cn

t)로 설계하여 문제를 해결할 수 있다.

 

문제는 좌표계 형태를 띄지만, 그래프 탐색을 할 필요가 전혀 없다. x, y좌표만 기억하면 되므로, 굳이 2차원 배열을 만들 것 없이, 1을 저장하는 벡터 하나, 2를 저장하는 벡터 하나 로 문제를 풀 수도 있다.

 

백트래킹은 해당 함수가 리턴되면 새로운 경우를 고려하기 위해 visited = false or pop_back을 통한 상태 초기화가 항상 일어나야 한다는 것을 유의하여야 한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int _MAX = 987654321;
int N, M, result = _MAX;
bool visited[101];
vector<pair<int, int>> house;
vector<pair<int, int>> market;
vector<pair<int, int>> survived;


void Recursion(int idx, int cnt){
    // end condition
    if(cnt == M){
        int dist = 0;
        for(int i=0; i<house.size(); i++){
            int x = house[i].first;
            int y = house[i].second;
            int d = _MAX;

            for(int j=0; j<survived.size(); j++)
                d = min(d, abs(x-survived[j].first) + abs(y-survived[j].second));
            dist += d;
        }
        result = min(result, dist);
        return;
    }

    for(int i=idx; i<market.size(); i++){
        if(visited[i])    continue;
        
        int x = market[i].first;
        int y = market[i].second;

        visited[i] = true;
        survived.push_back({x, y});
        Recursion(i, cnt + 1);
        survived.pop_back();
        visited[i] = false;
    }
}

int Solve(){
    cin >> N >> M;
    memset(visited, false, sizeof(bool)*M);
    // init
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int value;
            cin >> value;

            if(value == 1)          house.push_back({i, j});
            else if(value == 2)     market.push_back({i, j});
        }
    }

    // recursion
    Recursion(0, 0);

    return result;
}

int main(){
    ios_base::sync_with_stdio(false);   cin.tie(NULL);  cout.tie(NULL);
    int answer = Solve();
    cout << answer;
    return 0;
}