C -15686 치킨 배달

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

 

여러개의 A, B가 좌표선상에 있고 B를 m개만 유지하고 나머지를 삭제할때 (B를 m개 뽑았을때)

A에서 근처B에 가는 최소거리를 합해서 나오는 거리의합이 최소인 경우를 구하는 문제다.

 

큐로 두 A,B를 입력받아 좌표를 기억한다. 또 A,B의 개수를 세어 기록한다. (queue[][pos], rear)

그다음 그래프로 A-B사이의 거리를 기록할건데 B를 기준으로 A와 B의 최소 거리를 확인하려 한다.

그러므로 B->A로의 단방향 간선만 거리를 계산하여 저장한다.

graph[B][A] = B->A의 거리

(거리 계산은 문제의 규칙 distance = |r1-r2| + |c1-c2|을 따른다.)

#define abs(n) ((n)>0?(n):-(n))
#define distance(r1, c1, r2, c2) (abs(r1 - r2) + abs(c1 - c2))

 

이제 무식하게 (nCr을 현재 문제에 맞게 쓰면) chicken_cnt C m  -> 치킨집갯수에서 m개만큼 뽑는 조합을 구한다.

m개 뽑았을때(바닥조건) 치킨거리를 구하며, 치킨거리를 구하는 도중 그 시점에 도출된 최소치킨거리를 초과하면 더이상 연산하지않고 가지치기하는 식으로 구현했다. 

 

void dfs(int idx, int depth) {
    if(depth == M) {
        find_min();
        return;
    }
    for(int i=idx; i<chicken_cnt; i++) {
        if(select[i] == 0) {
            select[i] = 1;
            dfs(i, depth+1);
            select[i] = 0;
        }
    }
}

void find_min() {
    int tmp = 0;
    int find = 0;
    for(int i=0; i<house_cnt; i++) {
        tmp = INF;
        for(int j=0; j<chicken_cnt; j++) {
            if(select[j]) {
                tmp = min(tmp, graph[j][i]);
            }
        }
        find += tmp;
        if(find >= min_dist) return; //더이상 연산 무용
    }
    min_dist = find;
}

 

 

 

전체 코드

 

https://github.com/shirohebiui/BAEKJOON/blob/6561bd803ef51033314cbd4f88a98391ff78e7e4/%23DFS/G/15686(G5).c

 

 

 

PS. 백트래킹이 태그에 있는데 곰곰히 생각해보다가 마지막에 연산 가지치기에 큰 의미부여가 가능한가? 에 대해 궁금해서 if문의 가지치기를 빼고 min_dist = min(min_dist, find);로 바꿔봤는데 똑같은 시간으로 통과했다.

이게 백트래킹인 이유는 아마 그냥 조합(combination)의 구현자체에 백트래킹이 있다고 본듯하다.