BOJ 15686 : 치킨 배달 [C++]

 

15686번: 치킨 배달

 

 

치킨집을 선택하기 위한 백트래킹이 주요한 문제였다.

 

입력을 받을 때, pair 배열 house와 chicken에 가정집과 치킨집 각각의 좌표를 저장하며 개수를 카운트 했다.

이후 각 집에서 모든 치킨 집까지의 거리를 2차원 배열 dist에 저장

(row는 가정집 좌표 배열 house의 인덱스, column은 치킨집 좌표 배열 chicken의 인덱스)

 

백트래킹으로 치킨집 m개를 선택 후, 각 집에서부터 선택된 치킨집들을 대상으로 치킨 거리 계산하여 합산,

이 과정에서 기존의 정답보다 치킨 거리의 합이 커진다면 더 이상 계산하지 않고 return

return 되지 않고 모든 집의 치킨 거리를 구했다면 기존 정답과 비교하여 최신화.

 

 

코드

#include <iostream>
#include <math.h>

int m;
int h_index;
int c_index;
std::pair<int, int> house[100];
std::pair<int, int> chicken[13];
int dist[100][13] = {{0, }, };
int selected[13] = {0, };
int ans = 200000000;

void get_answer(int index, int cnt) {
    if (cnt == m) {
        int tmp_ans = 0;
        for (int i = 0; i < h_index; i++) {
            int tmp = 200000000;
            for (int j = 0; j < m; j++) {
                if (dist[i][selected[j]] < tmp) {
                    tmp = dist[i][selected[j]];
                }
            }
            tmp_ans += tmp;
            if (tmp_ans > ans) {
                return;
            }
        }
        if (tmp_ans < ans) {
            ans = tmp_ans;
        }
        return;
    }
    if (index == 0) {
        for (int i = index; i < c_index - m + 1; i++) {
            selected[cnt] = i;
            get_answer(i + 1, cnt + 1);
            selected[cnt] = -1;
        }
    } else {
        for (int i = index; i < c_index; i++) {
            selected[cnt] = i;
            get_answer(i + 1, cnt + 1);
            selected[cnt] = -1;
        }
    }
}

int main() {
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    std::ios::sync_with_stdio(false);

    int n = 0;
    std::cin >> n >> m;

    int cell = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> cell;
            if (cell == 1) {
                house[h_index] = {i, j};
                h_index++;
            } else if (cell == 2) {
                chicken[c_index] = {i, j};
                c_index++;
            }
        }
    }

    for (int i = 0; i < h_index; i++) {
        for (int j = 0; j < c_index; j++) {
            dist[i][j] = std::abs(house[i].first - chicken[j].first)
                         + std::abs(house[i].second - chicken[j].second);
        }
    }

    get_answer(0, 0);

    std::cout << ans << "\n";

    return 0;
}

 

 

분명 이 방법이 맞는 것 같은데도 시간 초과가 나서 한참을 고민했었다.

치킨집을 선택하는 백트래킹 과정에서 매개변수를 잘못 넣었다는걸 질문 탭 댓글을 보고서 알았다...

글을 쓰지 않는 동안 백트래킹으로 분류되는 'N과 M'  문제 시리즈를 풀었는데 그때도 실수가 많았었다.

백트래킹 풀 때 주의하자.