★ C - [백준 15686] 치킨 배달 (feat. 백트레킹, 시뮬레이션)

 

 

 

BOJ 15686 치킨 배달( https://www.acmicpc.net/problem/15686)

N × N 크기의 도시에서 MM개의 치킨집을 선택해 도시의 치킨 거리를 최소화하려고 합니다.

• 도시의 치킨 거리: 모든 집에 대해 가장 가까운 치킨집과의 거리의 합.
• 치킨집을 최대 M개 선택할 수 있으며, 이를 통해 도시의 치킨 거리를 최소화해야 합니다.

---

입력

1. 첫 번째 줄: N (도시 크기)와 M (유지할 최대 치킨집 개수)
2. 다음 N줄: 도시 정보 (0: 빈칸, 1: 집, 2: 치킨집)

---

출력

• 도시의 최소 치킨 거리를 출력합니다.

---

Checkpoint

 

1. 답을 확인한 문제 (실패)

 

설계를 잘 했다고 생각했으나, 예제 2, 예제3 예외처리를 고려하지 않은 설계로 실패하였습니다.

 

처음에 접근했던 방법은 각 집에서 제일 가까운 치킨 집을 찾아 카운팅하고, 카운팅 횟수를 기준으로 치킨집을 내림차순 정렬하였습니다. 그 후, M의 수 만큼 방문 횟수가 많은 치킨집을 뽑아내여 다시 최단거리 계산을 진행하였는데. 해당 방법은 

치킨집 방문 횟수가 내림차순으로 정렬할 수 있을 때, 즉 방문횟수가 동일한 치킨집이 없을 경우 가능했습니다. (예제 1, 2는 구현되었던 이유)

 

하지만 방문횟수가 동일한 치킨집이 있을 경우에도 최단거리를 계산해야하는데 이를 뒤늦게 발견하여 설계부터 잘못했던 문제였습니다. 

 

 

예를 들어 예제 3을 보았을 때, 모든 치킨집은 집한개과의 최소 거리를 유지하고 있기 때문에, count로 정렬했을 때, 정렬이 되지도 않고, 잘못된 치킨집으로 최소거리 계산이 들어가기 때문에, 예제는 3항 1열에 있는 치킨집을 기준으로 정렬하여 11이 나왔지만, 해당 방법으로 했을 때 첫번째 치킨집인 0항 1열이 선택되어 결과가 15으로 나옵니다.

 

2. 문제 내용 오해로 인해 백트래킹 알고리즘을 고려하지 않음 (잘못된 접근)

 

문제에서 최대 M을 선택할 수 있다라는 것에 집중하여 백트래킹으로 조합을 형성하는 것이 잘못된 방법이라고 오해했습니다. 왜냐하면 DFS로 백트래킹을 구현한다고 했을 때, 기저조건이 depth(level), 즉 노드 레벨 이 되는데 이를 M으로 설정하면 치킨 집이 M인 경우만 계산이 되어 잘못된 결과가 나온다고 판단하였습니다. 하지만 최대값이 M이라는 것과 집과 가까이 있는 치킨집이 선택되어 최단거리가 계산되는 것과 별도로 작동합니다. (이를 해설을 보고 알게 되었기 때문에 완벽한 실수)

 

 

예를 들어 예제1 을 보면, M이 3이고 기저 조건을 M으로 맞춰 노드 레벨이 M이 되었을 때 최소거리 계산을 한다고 한들, 각 집이 고르는 치킨집이 꼭 M이 아니라는 점입니다. 가장 가까운 것을 고르니 자연스럽게 5,5인 치킨집이 배제가 되었습니.

---

접근 방법

1. 모든 치킨집의 조합을 생성합니다.
   • M개의 치킨집만 유지.
   • 1개부터 M개까지 모든 경우를 고려.
2. 각 조합에 대해:
   • 모든 집에서 가장 가까운 치킨집까지의 거리를 계산.
   • 이를 합산하여 도시의 치킨 거리를 구합니다.
3. 도시의 치킨 거리 중 최소값을 출력합니다.

---

구현 세부사항

1. 입력 처리

• N×N 맵에서 집과 치킨집 위치를 분리하여 저장.
• 집은 최대 2×N, 치킨집은 최대 13개.

2. 조합 생성

• 백트래킹 또는 next_permutation을 통해 치킨집 조합을 생성.

3. 치킨 거리 계산

• 현재 선택된 치킨집 조합에 대해 각 집에서 가장 가까운 치킨집까지의 거리를 계산.

---

구현 코드

#include <stdio.h>
#include <stdlib.h>

int N, M;                  // 도시 크기, 남길 치킨집의 개수
int map[50][50];           // 도시 맵
int houses[100][2];        // 집 좌표
int house_count = 0;       // 집 개수
int chicken_count = 0;     // 치킨집 개수
int chickens[13][2];       // 치킨집 좌표
int selected[13] = {0};    // 선택된 치킨집 표시
int min_distance = 1e9;    // 최소 치킨 거리

// 거리 계산 함수
int calculate_chicken_distance() {
    int total_distance = 0;
    for (int i = 0; i < house_count; i++) {
        int hx = houses[i][0];
        int hy = houses[i][1];
        int min_dist = 1e9;
        for (int j = 0; j < chicken_count; j++) {
            if (selected[j]) {
                int cx = chickens[j][0];
                int cy = chickens[j][1];
                int dist = abs(hx - cx) + abs(hy - cy);
                if (dist < min_dist) {
                    min_dist = dist;
                }
            }
        }
        total_distance += min_dist;
    }
    return total_distance;
}

// 백트래킹으로 치킨집 조합 선택
void dfs(int idx, int cnt) {
    if (cnt == M) {
        // 현재 선택된 치킨집으로 치킨 거리 계산
        int distance = calculate_chicken_distance();
        if (distance < min_distance) {
            min_distance = distance;
        }
        return;
    }

    for (int i = idx; i < chicken_count; i++) {
        if (!selected[i]) {
            selected[i] = 1;
            dfs(i + 1, cnt + 1);
            selected[i] = 0;
        }
    }
}

int main() {
    // 입력 받기
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 1) {
                houses[house_count][0] = i;
                houses[house_count][1] = j;
                house_count++;
            } else if (map[i][j] == 2) {
                chickens[chicken_count][0] = i;
                chickens[chicken_count][1] = j;
                chicken_count++;
            }
        }
    }

    // 백트래킹으로 최소 치킨 거리 계산
    dfs(0, 0);

    // 결과 출력
    printf("%d\n", min_distance);
    return 0;
}

---

 

1) 전역 변수 초기화

int N, M;                  // 도시 크기(N x N), 최대 남길 치킨집의 개수
int map[50][50];           // 도시 맵 (0: 빈칸, 1: 집, 2: 치킨집)
int houses[100][2];        // 집 좌표 (최대 100개)
int house_count = 0;       // 집 개수
int chicken_count = 0;     // 치킨집 개수
int chickens[13][2];       // 치킨집 좌표 (최대 13개)
int selected[13] = {0};    // 선택된 치킨집 표시 (1: 선택됨, 0: 선택되지 않음)
int min_distance = 1e9;    // 최소 치킨 거리 (최초 큰 값으로 초기화)

• map:
  • 도시의 각 위치를 저장하는 배열.
  • 1: 집, 2: 치킨집.
• houses와 chickens:
  • 각각 집과 치킨집의 좌표를 저장하는 배열.
• selected:
  • 백트래킹 시 선택된 치킨집을 표시하는 배열.
• min_distance:
  • 현재까지의 최소 치킨 거리를 저장하는 변수.

---

2) 거리 계산 함수

int calculate_chicken_distance() {
    int total_distance = 0;
    for (int i = 0; i < house_count; i++) {
        int hx = houses[i][0];
        int hy = houses[i][1];
        int min_dist = 1e9;
        for (int j = 0; j < chicken_count; j++) {
            if (selected[j]) {
                int cx = chickens[j][0];
                int cy = chickens[j][1];
                int dist = abs(hx - cx) + abs(hy - cy);
                if (dist < min_dist) {
                    min_dist = dist;
                }
            }
        }
        total_distance += min_dist;
    }
    return total_distance;
}

작동 방식

1. 모든 집에 대해, 선택된 치킨집들과의 거리를 계산.
2. 각 집에서 가장 가까운 치킨집까지의 거리를 선택.
3. 모든 집의 거리 합계를 반환.

예시

• 집: (0,1),(1,3), 치킨집: (1, 1), (2, 2).
• 선택된 치킨집: (1,1).
  • 집 (0, 1): 거리 1 ((1,1)(1, 1)).
  • 집 (1, 3): 거리 2 ((1,1)(1, 1)).
• 총 거리 = 1 + 2 = 3.

---

3) 백트래킹 함수

void dfs(int idx, int cnt) {
    if (cnt == M) {
        // 현재 선택된 치킨집으로 치킨 거리 계산
        int distance = calculate_chicken_distance();
        if (distance < min_distance) {
            min_distance = distance;
        }
        return;
    }

    for (int i = idx; i < chicken_count; i++) {
        if (!selected[i]) {
            selected[i] = 1; // 치킨집 선택
            dfs(i + 1, cnt + 1);
            selected[i] = 0; // 선택 해제
        }
    }
}

작동 방식

1. 조합 탐색:
   • 현재 치킨집을 선택하거나 선택하지 않고 다음 단계로 이동.
   • M개의 치킨집을 선택하면 거리 계산 수행.
2. 탐색 종료 조건:
   • M개의 치킨집을 선택했을 때 탐색 종료.
3. 선택된 치킨집 조합마다 최소 치킨 거리를 갱신.

예시

• 치킨집: (1, 1), (2, 2), (3, 3), M = 2.
• 탐색 순서:
  1. (1, 1), (2, 2)
  2. (1, 1), (3, 3)
  3. (2, 2), (3, 3)

---

4) 메인 함수

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 1) {
                houses[house_count][0] = i;
                houses[house_count][1] = j;
                house_count++;
            } else if (map[i][j] == 2) {
                chickens[chicken_count][0] = i;
                chickens[chicken_count][1] = j;
                chicken_count++;
            }
        }
    }

    // 백트래킹으로 최소 치킨 거리 계산
    dfs(0, 0);

    // 결과 출력
    printf("%d\n", min_distance);
    return 0;
}

작동 방식

1. 입력 처리:
   • N×N 맵을 읽어들여 집과 치킨집의 좌표를 각각 houses와 chickens 배열에 저장.
2. 백트래킹 시작:
   • dfs(0, 0) 호출로 치킨집 조합 탐색 시작.
3. 결과 출력:
   • 최소 치킨 거리 min_distance를 출력.

---

코드 실행 예제

입력

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

출력

5

과정

1. 가능한 치킨집 조합:
   • (1, 2), (2, 2), (4, 4)
2. 도시의 치킨 거리 계산:
   • 집 (0, 2): 거리 1 ((1,2)).
   • 집 (1, 4): 거리 3 ((4, 4)).
   • 집 (3, 2): 거리 1 ((2, 2)).
3. 최소 치킨 거리 = 1 + 3 + 1 = 5.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.