백준 치킨배달

백준 15686번 치킨 배달

문제를 읽어보고 치킨집 개수 N개에서 M개를 포함한 모든 조합을 탐색하면 문제를 풀 수 있겠다는 생각이 들었다. 하지만 백트래킹 알고리즘에 대한 이해가 없었기에, N과 M(1) 문제를 먼저 풀어본 뒤 본 문제에 대한 코드를 작성했다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Point> chickens = new ArrayList<>();
    static ArrayList<Point> homes = new ArrayList<>();
    static int n;
    static int m;
    static boolean[] deleted;
    static int minValue = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int a = sc.nextInt();
                if (a == 1) {
                    homes.add(new Point(j, i));
                } else if (a == 2) {
                    chickens.add(new Point(j, i));
                }
            }
        }
        deleted = new boolean[chickens.size()];
        bfs(chickens.size());
        System.out.println(minValue);
    }

    static void bfs(int chickenCount) {
        if (chickenCount == m) {
            // 종료 조건
            int result = cal();
            minValue = Math.min(result, minValue);
            return;
        }

        for (int i = 0; i < chickens.size(); i++) {
            if (!deleted[i]) {
                deleted[i] = true;
                bfs(chickenCount - 1);
                deleted[i] = false;
            }
        }
    }

    static int cal() { // 도시의 치킨 거리를 구하는 메소드
        int sum = 0;
        for (int i = 0; i < homes.size(); i++) {
            Point home = homes.get(i);
            sum += cal2(home);
        }
        return sum;
    }

    static int cal2(Point p) { // 집의 치킨 거리를 구하는 메소드
        int result = 101;
        for (int i = 0; i < chickens.size(); i++) {
            if (!deleted[i]) {
                Point chicken = chickens.get(i);
                int tmp = Math.abs(p.x - chicken.x) + Math.abs(p.y - chicken.y);
                if (result > tmp) {
                    result = tmp;
                }
            }
        }
        return result;
    }
}

class Point {
    int x;
    int y;

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

채점 결과 시간 초과가 나왔다. 어떤 점이 문제인가 생각해보다 해결이 안 돼 다른 사람의 풀이를 찾아보고 문제점을 발견했다. N과 M(1) 문제를 푼 직후 풀어서 그런지, 해당 문제에서 의미 없는 조합까지 탐색하도록 코드를 작성했다. 폐업하지 않을 치킨집의 조합을 1번-2번-5번, 2번-1번-5번, 5번-1번-2번의 조합까지 탐색했었다. 하지만 위 3가지 조합은 모두 동일한 도시의 치킨 거리를 반환하여 재탐색할 필요가 없는 조합이었다. 치킨집은 중복되지 않기 때문에 탐색에 포함된 치킨집은 더 이상 포함할 필요가 없었는데, N과 M(1) 문제를 해결했던 탐색 방법으로 접근했던 게 문제였었다.

정답 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Point> chickens = new ArrayList<>();
    static ArrayList<Point> homes = new ArrayList<>();
    static int n;
    static int m;
    static boolean[] deleted;
    static int minValue = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int a = sc.nextInt();
                if (a == 1) {
                    homes.add(new Point(j, i));
                } else if (a == 2) {
                    chickens.add(new Point(j, i));
                }
            }
        }
        deleted = new boolean[chickens.size()];
        bfs(0, 0);
        System.out.println(minValue);
    }

    static void bfs(int start, int chickenCount) {
        if (chickenCount == m) {
            // 종료 조건
            int result = cal();
            minValue = Math.min(result, minValue);
            return;
        }

        for (int i = start; i < chickens.size(); i++) {
            if (!deleted[i]) {
                deleted[i] = true;
                bfs(i + 1, chickenCount + 1);
                deleted[i] = false;
            }
        }
    }

    static int cal() { // 도시의 치킨 거리를 구하는 메소드
        int sum = 0;
        for (Point home : homes) {
            sum += cal2(home);
        }
        return sum;
    }

    static int cal2(Point p) { // 집의 치킨 거리를 구하는 메소드
        int result = 101;
        for (int i = 0; i < chickens.size(); i++) {
            if (deleted[i]) {
                Point chicken = chickens.get(i);
                result = Math.min(Math.abs(p.x - chicken.x) + Math.abs(p.y - chicken.y), result);
            }
        }
        return result;
    }
}

class Point {
    int x;
    int y;

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