[15686] 치킨 배달 문제 리뷰 및 개선

 

---

 

1. 문제 개요

백준 15686번 '치킨 배달' 문제는 도시의 치킨집 중 m개를 선택하여 도시의 치킨 거리를 최소화하는 문제입니다. 치킨 거리란 집과 가장 가까운 치킨집 사이의 거리로 정의됩니다. 목표는 주어진 치킨집 중 m개의 치킨집을 선택하여 모든 집의 치킨 거리의 합을 최소화하는 것입니다.

---

2. 기존 코드 분석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class ChicBranch {
    static List<int[]> homeList = new ArrayList<>();
    private final List<Integer> distToHome = new ArrayList<>();

    private int totalDist = 0;
    private final int y, x;

    ChicBranch(int y, int x) {
        this.y = y;
        this.x = x;
    }

    public int[] getDistToHome() {
        return distToHome.stream().mapToInt(Integer::intValue).toArray();
    }
    public int getTotalDist() {
        return totalDist;
    }
    public void update() {
        for (int[] i : homeList) {
            int num = Math.abs(y - i[0]) + Math.abs(x - i[1]);
            distToHome.add(num);
            totalDist += num;
        }
    }
    static void addHome(int y, int x) {
        homeList.add(new int[] {y, x});
    }
}
public class Main {
    private static int total = Integer.MAX_VALUE;
    private static final List<ChicBranch> chicBranchList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);     // [2,50]
        int m = Integer.parseInt(input[1]); //  [1,13]

        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                int temp = Integer.parseInt(input[j]);
                if (temp == 1) ChicBranch.addHome(i, j);
                else if (temp == 2) chicBranchList.add(new ChicBranch(i, j));
            }
        }

        for (ChicBranch chic : chicBranchList)
            chic.update();
        for (int i = 0; i < chicBranchList.size(); i++) {
            ChicBranch c = chicBranchList.get(i);
            func(m-1, i+1, c.getTotalDist(), c.getDistToHome());
        }
        System.out.println(total);
    }

    private static void func(int depth, int start, int currentTotal, int[] minDistances) {
        if (depth < 1) {
            total = Math.min(total, currentTotal);
            return;
        }
        int[] buf = new int[minDistances.length];

        for (int i = start; i < chicBranchList.size(); i++) {
            System.arraycopy(minDistances, 0, buf, 0, minDistances.length);
            int[] dist = chicBranchList.get(i).getDistToHome();
            int sum = currentTotal;

            for (int j = 0; j < dist.length; j++) {
                if (dist[j] < buf[j]) {
                    sum = sum + dist[j] - buf[j];
                    buf[j] = dist[j];
                }
            }
            func(depth - 1, i+1, sum, buf);
        }
    }
}

기존 코드는 전체 도시를 스캔하여 집과 치킨집을 리스트에 저장하고, 각 치킨집에 대해 모든 집과의 거리를 계산한 후, m개의 치킨집을 선택하여 도시의 치킨 거리를 최소화하는 방식입니다.

체크리스트 기반 코드 평가

• 가독성:
  • 변수명과 함수명이 직관적이지 않아 코드를 이해하기 어렵습니다.
  • 주석이 부족하여 코드의 의도를 파악하기 어렵습니다.
• 효율성:
  • 각 치킨집에 대해 모든 집과의 거리를 매번 계산하므로 시간 복잡도가 높습니다.
  • 불필요한 연산이 존재합니다.
• 확장성:
  • 유지보수하기 어렵고, 다른 문제에 적용하기 어렵습니다.
• 명확성:
  • 문제의 의도를 코드가 잘 반영하고 있습니다.

 

---

 

3. 코드 풀이 과정

기존 코드에서 ChicBranch 클래스는 치킨집의 위치와 집까지의 거리를 저장하며, Main 클래스에서 전체 로직을 처리합니다.

1. 도시를 스캔하여 집과 치킨집을 리스트에 저장합니다.
2. 각 치킨집에 대해 모든 집과의 거리를 계산합니다.
3. 재귀 함수를 사용하여 m개의 치킨집을 선택하고, 도시의 치킨 거리를 계산합니다.

 

---

4. 코드 개선 및 최적화

개선 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m;
    static List<int[]> homes = new ArrayList<>();
    static List<int[]> chickens = new ArrayList<>();
    static int[][] distances;
    static int minDistance = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int value = Integer.parseInt(st.nextToken());
                if (value == 1) homes.add(new int[]{i, j});
                else if (value == 2) chickens.add(new int[]{i, j});
            }
        }

        distances = new int[chickens.size()][homes.size()];
        for (int i = 0; i < chickens.size(); i++) {
            for (int j = 0; j < homes.size(); j++) {
                distances[i][j] = Math.abs(chickens.get(i)[0] - homes.get(j)[0]) + Math.abs(chickens.get(i)[1] - homes.get(j)[1]);
            }
        }

        selectChickens(new boolean[chickens.size()], 0, 0);
        System.out.println(minDistance);
    }

    static void selectChickens(boolean[] selected, int count, int start) {
        if (count == m) {
            int totalDistance = 0;
            for (int i = 0; i < homes.size(); i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < chickens.size(); j++) {
                    if (selected[j]) {
                        min = Math.min(min, distances[j][i]);
                    }
                }
                totalDistance += min;
            }
            minDistance = Math.min(minDistance, totalDistance);
            return;
        }

        for (int i = start; i < chickens.size(); i++) {
            selected[i] = true;
            selectChickens(selected, count + 1, i + 1);
            selected[i] = false;
        }
    }
}

 

개선 후 평가

• 가독성:
  • 변수명과 함수명을 직관적으로 수정하여 코드의 가독성을 높였습니다.
  • 주석을 추가하여 코드의 의도를 명확히 하였습니다.
• 효율성:
  • 거리 계산을 미리 수행하여 불필요한 연산을 줄였습니다.
• 확장성:
  • 코드 구조를 단순화하여 유지보수성을 높였습니다.
• 명확성:
  • 문제의 의도를 더욱 명확히 반영하였습니다.

---

5. 추가 최적화 가능성 탐색

 

---

 

6. 결론 및 마무리

이번 코드 리뷰를 통해 코드의 가독성, 효율성, 확장성, 명확성을 고려하여 개선할 수 있었습니다. 이 과정에서 중요한 것은 코드의 명확한 의도 전달과 불필요한 연산의 제거입니다. 비슷한 문제를 풀 때 이러한 원칙을 적용하면 더욱 효율적인 코드를 작성할 수 있습니다.

행복한 코딩되세요! 🚀

m개의 치킨집을 고르는 로직 중간에서 거리합이 total 보다 크면 바로 종료시키는 실수를 하고 알아차리지 못해 계속 틀렸다. 초기에 값이 크고, 점점 줄여나가기 때문에 실시간 최솟값과 비교하면 오답일 수밖에.. 지우니까 돌아가는구나