백준 15686번 치킨 배달 JAVA

링크텍스트

설명

처음에는 dfs로 depth 조건이 맞는다면 bfs를 통해 최소값을 구하려했지만 시간초과가 나왔다.
그래서 구글링해서 다시 풀었다. 2개의 List 각각 houses, chickens를 선언하고 각각의 좌표를 저장한다. 그리고 백트래킹을 통해 최소값을 구한다.

코드

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[][] arr;
    static boolean [] check;
    static ArrayList<position> houses = new ArrayList<>();
    static ArrayList<position> chickens = new ArrayList<>();
    static int result = 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 = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) houses.add(new position(i, j));
                if (arr[i][j] == 2) chickens.add(new position(i, j));
            }
        }

        check = new boolean[chickens.size()];
        dfs(0,0);

        System.out.println(result);
    }

    public static void dfs(int depth, int start) {
        if (depth == m) {
            int total = 0;

            for (int i = 0; i < houses.size(); i++) {
                position house = houses.get(i);
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < chickens.size(); j++) {
                    if (check[j]) {
                        position chicken = chickens.get(j);
                        int distance = Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y);
                        min = Math.min(min, distance);
                    }
                }
                total += min;
            }
            result = Math.min(result, total);
            return;
        }
        for(int i=start; i<chickens.size(); i++){
            if(!check[i]){
                check[i]=true;
                dfs(depth+1,i+1);
                check[i]=false;
            }
        }
    }
    static class position {
        int x;
        int y;

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

시간 초과 난 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[][] arr;
    static int[][] copyarr;
    static boolean[][] check;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int two = 0;
    static int result = 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];
        check = new boolean[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) check[i][j] = true;
                if (arr[i][j] == 2) two++;
            }
        }

        dfs(0);
        System.out.println(result);
    }

    public static void dfs(int depth) {
        if (depth == two - m) {
            bfs();
            return;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] == 2) {
                    arr[i][j] = 0; 
                    dfs(depth + 1);
                    arr[i][j] = 2;
                }
            }
        }
    }

    public static void bfs() {
        Queue<position> q = new LinkedList<>();
        copyarr = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                copyarr[i][j] = arr[i][j];
                if (copyarr[i][j] == 2) {
                    q.offer(new position(i, j)); 
                }
            }
        }

        int totalDistance = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (copyarr[i][j] == 1) { 
                    int minDistance = Integer.MAX_VALUE;

                    for (position chicken : q) {
                        int distance = Math.abs(chicken.x - i) + Math.abs(chicken.y - j);
                        minDistance = Math.min(minDistance, distance);
                    }

                    totalDistance += minDistance;
                }
            }
        }

        result = Math.min(result, totalDistance); 
    }

    static class position {
        int x;
        int y;

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