피자 배달거리 DFS 시간초과 문제

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

class Main {
    static int N, M, dis, min, sum, answer;
    static ArrayList<Point> houses, pizzas;
    static Point[] spizzas;
    static int[] ch;

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        spizzas = new Point[M];
        houses = new ArrayList<>();
        pizzas = new ArrayList<>();
        answer = Integer.MAX_VALUE;


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int tmp = sc.nextInt();
                if (tmp == 1) {
                    houses.add(new Point(i, j));
                }
                if (tmp == 2) {
                    pizzas.add(new Point(i, j));
                }

            }
        }
        ch = new int[pizzas.size()];
        T.DFS(0);
        System.out.println(answer);
    }

    void DFS(int L) {
        if (L == M) {
            sum = 0;
            for (Point house : houses) {
                min = Integer.MAX_VALUE;
                for (Point pizza : spizzas) {
                    dis = Math.abs(house.x - pizza.x) + Math.abs(house.y - pizza.y);
                    if (Math.min(min, dis) == dis) {
                        min = dis;
                    }
                }
                sum += min;
            }
            if (Math.min(sum, answer) == sum) {
                answer = sum;
            }
        } else {
            for (int i = 0; i < pizzas.size(); i++) {
                if (ch[i] == 0) {
                    ch[i] = 1;
                    spizzas[L] = pizzas.get(i);
                    DFS(L + 1);
                    ch[i] = 0;
                }
            }
        }

    }
}

class Point {
    int x;
    int y;

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

선생님의 풀이와는 다르게 체크드리스트를 만들어 DFS구현을 하였고 답이 잘 나오긴 하는데 채점사이트에서는 시간초과 문제가 나오네요 ㅜㅜ 혹시 문제가 어떤 것인지 알 수 있을까요??

안녕하세요, 인프런 AI 인턴입니다.

민표님, 피자 배달거리 문제를 DFS로 풀이하신 부분 잘 보았습니다.
설명해주신 코드를 살펴보니, 피자집의 모든 조합을 구하여 각각의 조합에 대해 최소 거리의 합을 구하는 방식으로 작성하셨네요. 이와 같은 방식은 M개를 선택하는 모든 조합에 대해 검사하기 때문에, 조합의 수가 많아질 경우 매우 많은 경우의 수를 계산해야 해서 시간 초과가 발생할 수 있습니다.

가능한 조합의 수가 많지 않을 때는 모든 경우를 다 검사하는 방식이 가능할 수 있으나, 피자집의 수가 많아져 경우의 수가 기하급수적으로 증가하면 DFS를 사용하는 백트래킹이 중요해집니다. 즉, 가능하지 않은 경우를 빠르게 건너뛰어 계산량을 줄이는 것이 중요한데요. 현재 구현하신 DFS 알고리즘은 불필요한 조합까지 모두 탐색하는 것으로 보입니다.

시간 초과 문제를 해결하기 위해 몇 가지 방법을 시도해볼 수 있습니다:
1. 현재 선택한 피자집 조합이 이미 구한 최소값보다 클 경우 그 이후의 조합을 탐색하지 않도록 가지치기를 수행합니다.
2. 피자집의 수가 큰 경우, 다른 알고리즘(예: 분기 한정법)을 고려하거나, 휴리스틱한 방법을 사용하여 탐색 범위를 제한할 수 있습니다.
3. 최적화 문제인 경우 동적 계획법(Dynamic Programming)을 사용하여 중복 계산을 줄이는 방법도 있습니다.

DFS 함수 내부에서 이 조건을 검사하고 조기에 함수 호출을 종료하도록 코드를 수정해 보세요.
효율적인 알고리즘 구현을 위해 성능을 분석하고 개선하는 작업은 지속적으로 이뤄져야 합니다. 시간 초과 문제를 해결하는 과정에서 프로그래밍 실력이 한 단계 성장하시리라 믿습니다. 파이팅입니다!

인프런 커뮤니티 질문&답변