[알고리즘] 백준 15686번 치킨배달 ::우유

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

코드 설명

BFS로 모든 경로를 다 찾으려고 하면 당연히 시간초과가 나버린다.
집에서 치킨집의 조합의 경우의 수 만큼 거리를 백트래킹으로 구하여 그것의 최소값을 구하면 된다.
(이 아이디어를 생각해내는데 꽤 오래걸렸다..)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] arr;
    static boolean[] visited;
    static ArrayList<Node> chickenList = new ArrayList<>();
    static ArrayList<Node> houseList = new ArrayList<>();
    static int answer = 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());

        arr = new int[N + 1][N + 1];


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 1)
                    houseList.add(new Node(i, j));

                if (arr[i][j] == 2)
                    chickenList.add(new Node(i, j));
            }
        }

        visited = new boolean[chickenList.size()];

        DFS(0, 0);
        System.out.println(answer);
    }

    public static void DFS(int idx, int cnt) {
        if (cnt == M) {

            int res = 0;

            for (int i = 0; i < houseList.size(); i++) {
                int sum = Integer.MAX_VALUE;
                for (int j = 0; j < chickenList.size(); j++) {
                    if (visited[j]) {
                        // 각 치킨집에서 집까지의 거리의 최소값
                        int distance = Math.abs(chickenList.get(j).y - houseList.get(i).y) + Math.abs(chickenList.get(j).x - houseList.get(i).x);
                        sum = Math.min(sum, distance);
                    }
                }
                res += sum;
            }
            answer = Math.min(answer, res);
            return;
        }

        for (int i = idx; i < chickenList.size(); i++) {
            visited[i] = true;
            DFS(i + 1, cnt + 1);
            visited[i] = false;
        }
    }

    public static class Node {
        int x;
        int y;

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

        }
    }
}