[C언어 백준 풀이][Gold V] 15686번 : 치킨 배달 (재귀함수, 브루트포스 알고리즘)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 Gold V 난이도에 해당하는 문제인 '15686번 : 치킨 배달'의 풀이 코드와 해설을 다루고 있습니다.

 

 

백준에서 같은 티어의 문제들이라도 아무 문제나 푸는 것보다도 Solved.ac에서 선별된 문제들을 푸는 것이 낫다고 판단해서 풀이하고 있습니다.

그래서 Class 문제들을 위주로 해결하고 있는데, Class 3까지는 어느 정도 풀어서 Class 4를 따기 위해 남은 1문제인 치킨 배달 문제를 풀이해보도록 하겠습니다.

 

 

15686번 : 치킨 배달

 

문제가 아주 긴데, 요약하면 1은 집, 2는 치킨집을 의미하는 지도가 입력될 때, 여러 개의 치킨 집 중에서 오직 M개의 치킨집만을 남기고 나머지는 없앤다고 하면 각 집들에서 가장 가까운 치킨집까지의 거리들의 합이 최소가 되는 합을 출력하는 문제입니다. (이 때 거리는 택시 기하로써의 거리를 의미함)

 

처음에는 이 문제의 알고리즘 분류조차도 확인하지 않고 BFS로 풀이를 시도했습니다. (물론 실패하고 나서도 확인 안했고 다 풀고나서 확인했습니다.)

그런데 이 문제는 BFS나 탐색으로 풀이하는 문제가 아니었습니다.

일반적으로 맵에 대한 정보가 주어지는 문제를 보고 바로 탐색으로 접근하는 습관을 고치도록 도와준 문제였다고 생각합니다.

 

(** 주의 : 실패 코드입니다. 작동은 하지만 시간초과 발생.

    성공 코드는 하단에 있음.)

#include <stdio.h>

int N, M, house_count = 0, min_sum = 1000000;
int map[55][55] = {0, }, check[55][55] = {0, }, house[2505][2], chicken[15][2];
int abs(int a) { return a>=0?a:-a; }

void distance() {
    int sum = 0, min_dist, dist;
    for(int i=0; i<house_count; i++) {
        min_dist = 100;
        for(int j=0; j<M; j++) {
            dist = abs(house[i][0]-chicken[j][0]) + abs(house[i][1]-chicken[j][1]);
            if(dist < min_dist) min_dist = dist;
        }
        sum += min_dist;
    }
    if(sum < min_sum) min_sum = sum;
}

void select(int left) {
    if(left <= 0) {
        int count = 0;
        for(int i=1; i<=N; i++)
            for(int j=1; j<=N; j++)
                if(check[i][j]) {
                    chicken[count][0] = i;
                    chicken[count][1] = j;
                    count++;
                }
        distance();
    }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if(map[i][j] == 2 && !check[i][j]) {
                check[i][j] = 1;
                select(left-1);
                check[i][j] = 0;
            }
}

int main() {
    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] == 1) {
                house[house_count][0] = i;
                house[house_count][1] = j;
                house_count++;
            }
        }
    select(M);
    printf("%d", min_sum);
}

 

위의 코드는 초기에 시도한 코드입니다.

select 함수를 재귀적으로 돌려서 M개의 치킨집을 선택하고, 선택이 끝나면 거리를 계산하는 방식을 채택했습니다.

그러나 이 방법대로는 시간이 너무 많이 걸린다는 단점이 있어, 결국 시간초과를 받게 되었습니다.

그래서 지도를 이용해서 무언가를 계산하는게 아니라 입력을 받는 즉시 거리들만을 저장해서, 치킨집을 선별하는 즉시 거리를 (계산하지 않고) 꺼내와서 합산하도록 하였습니다.

 

#include <stdio.h>

int N, M, type, house_count = 0, chicken_count = 0, min_sum = 10000000;
int house[105][2], chicken[2505][2], check[2505] = {0, }, selected_chicken[15], dist[105][2505];
int abs(int a) { return a>=0?a:-a; }

void select(int left, int recent) {
    if(left <= 0) {
        int sum = 0, min_dist;
        for(int i=0; i<house_count; i++) {
            min_dist = 100;
            for(int j=0; j<M; j++)
                if(dist[i][selected_chicken[j]] < min_dist) min_dist = dist[i][selected_chicken[j]];
            sum += min_dist;
        }
        if(sum < min_sum) min_sum = sum;
        return;
    }
    for(int i=recent; i<chicken_count; i++) {
        if(!check[i]) {
            selected_chicken[M-left] = i;
            check[i] = 1;
            select(left-1, i+1);
            check[i] = 0;
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) {
            scanf("%d", &type);
            if(type == 1) {
                house[house_count][0] = i;
                house[house_count][1] = j;
                house_count++;
            }
            else if(type == 2) {
                chicken[chicken_count][0] = i;
                chicken[chicken_count][1] = j;
                chicken_count++;
            }
        }
    for(int i=0; i<house_count; i++)
        for(int j=0; j<chicken_count; j++) dist[i][j] = abs(house[i][0]-chicken[j][0]) + abs(house[i][1]-chicken[j][1]);
    select(M, 0);
    printf("%d", min_sum);
}

 

필요한 부분만 작성하였음에도 상당히 코드가 길어지게 되었는데, 어쩔 수 없다고 생각합니다.

우선 house는 집의 좌표를 저장하며 집은 최대 2N개 이하로만 입력된다고 하였으므로 크기를 작게 잡았습니다.

chicken은 치킨집의 좌표를 저장하며 개수 제한이 입력되지 않았으므로 넉넉하게 크기를 잡았습니다.

둘의 좌표들을 입력받는 즉시 dist 배열에 이들간의 모든 거리를 계산하여 저장하였습니다.

 

select 함수를 재귀적으로 돌려서 M개의 치킨집이 선택이 끝나게 되면 dist 배열에 저장된 값들 중 M개의 치킨집들과 연관된 거리만을 가져와 최솟값을 계산하도록 하였습니다.

더 자세한 설명이나 원리는 코드를 참고해주시면 감사하겠습니다.

 

 

제출 결과, 시간 제한을 염려했으나 0ms라는 사실상 거의 시간 소요를 하지 않고 문제를 해결할 수 있었습니다.

 

 

---

 

문제 해결 결과, 이 문제를 마지막으로 Class 4를 취득할 수 있었습니다.

그러나 바로 Class 5 문제들을 접근하지 않고 에센셜 문제들을 조금 더 풀어보고 넘어가도록 하겠습니다.