백준 15686번 치킨 배달 (C++)

문제 설명

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

15686번: 치킨 배달

 

문제 해결

 

그리디가 아닌, 완전 탐색을 해야 풀리는 문제이다. 이 점만 알고 접근한다면 그리 어려운 문제는 아니다. 

문제 조건을 보면 알 수 있듯이, M, N의 수가 그리 높지 않아 완전 제곱으로 충분히 문제를 해결할 수 있다. 

 

과정은 다음과 같다.

1. M개 치킨집을 뽑는다. (조합의 원리를 생각하면 된다.)

2. M개에 대한 치킨 거리를 계산한다. 

3. 최솟값을 갱신한다.

 

문제에서 '최대 M개'라는 말이 다소 모호하게 느껴졌지만,  풀면서 크게 문제가 되지는 않았다. 

 

트러블슈팅

 

사실 맞는 방향으로 문제를 풀었음에도 불구하고, 문제를 푸는 데에 시간이 굉장히 오래 걸렸다. 

백준 질문 게시판에 있는 TC가 모두 맞는 데에도 불구하고 30퍼 대에서 계속 '틀렸습니다.'가 나왔는데, 그 원인을 찾을 수 없어서 였다.

그 문제를 해결하기 위해 꽤나 다양한 방법으로 풀었으나, 계속 같은 오류에 부딪혔다. 

 

그 오류의 원인은 DFS 함수 내부에 있었다. 원래는 인덱스 벗어나는걸 방지하기 위해 for 문 이전에 다음과 같은 코드를 넣었었다. 

    if ((idx + 1) >= len) //범위 초과
        return ;

하지만 이 코드는 두가지 면에서 문제가 있었다. 

 

1. idx + 1 == len인 경우에도 밑 for문을 돌려야한다. 즉 과하게 범위 제한을 걸어서 꼭 탐색해야 하는 부분을 탐색하지 못한 것이다. 

2. 애초에 for문 안에서 인덱스를 확인하므로 위 조건문을 걸어줄 필요가 없었다. 

 

간단한 에러 코드임에도 오랬동안 발견하지 못한 것은, DFS 재귀에 대한 이해, 코드에 대한 이해 부족에 기계적으로 문제를 풀다가 생겨난 오류로 판단된다. 앞으로 무지성으로 예제코드 넣으면서 왜 안돼를 외치는 습관을 멈추고, 차분하게 내 코드를 봐야겠다는 교훈을 얻을 수 있었던 문제였다. 

 

나는 엉뚱한 곳을 문제지점이라고 판단하고 미리 최솟값을 저장해두기, vector 대신 배열로 방문 체크하기, 중복 방지 코드 달아주기 .. 등 다양한 버전으로 풀어보았는데, 처음에 풀었던 버전으로 코드를 남겨본다. 

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <climits>

using namespace std;
int map[51][51];
vector <pair <int, int> > ckn;
vector <pair <int, int> > house;

//1. 일단 M개 치킨집을 뽑는다. 
//2. M개에 대한 치킨 거리를 계산한다.
//3. 가장 최솟값을 구한다. 
int n,m;
int len;
int res_dis = INT_MAX;

int get_chicken_dis(vector <int> res)
{
    int house_all = 0;
    for (int i = 0; i < house.size(); i++)
    {
        int min_house = INT_MAX;
        for (int j = 0; j < res.size(); j++)
        {
            int tmp = abs(house[i].first - ckn[res[j]].first) +   abs(house[i].second - ckn[res[j]].second);
            if (min_house > tmp)
                min_house = tmp;
        }
        house_all += min_house;
        if (house_all > res_dis)
        {
            house_all = INT_MAX;
            break ;
        }
    }
    return (house_all);
}

void dfs(vector <int>& res, int idx, int cnt)
{
    if (cnt == m)
    {
        int tmp = get_chicken_dis(res);
        if (res_dis > tmp)
            res_dis = tmp;
        return ;
    }
    for (int i = idx; i < len; i++)
    {     
        res.push_back(i);
        dfs(res, i + 1, cnt + 1);
        res.pop_back();
    }
}

int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2)
                ckn.push_back(make_pair(i, j));
            if (map[i][j] == 1)
                house.push_back(make_pair(i, j));

        }
    }
    len = ckn.size();
    vector <int> res;
    dfs(res, 0, 0);
    cout << res_dis << "\n";
}