백준 15686번 치킨 배달 (JAVA)

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

15686번: 치킨 배달

 

저는 맨 처음에 DFS와 BFS를 이용해 문제를 해결하였습니다. DFS를 이용해 M개의 치킨집을 선택하고 각각의 집(1)에서 BFS를 통해 각 치킨집의 최소값을 구했습니다. 이렇게 했을때 채점 기준으로 2초가 넘었습니다.

문제를 다시 보니, 각각의 집에서 BFS를 할 필요없이 처음에 각 집의 좌표를 구하고 선택한 치킨집과 좌표를 빼서 최소값을 구하면 되었습니다. 이렇게 했을때 채점 기준 1초가 나오지 않았습니다.

 

package BOJ.Simulation;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_15686_2 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Function<String, Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[][] map = new int[n][n];
        List<int[]> shop = new ArrayList<>();
        List<int[]> house = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                map[i][j] = stoi.apply(st.nextToken());
                if (map[i][j] == 2) {
                    shop.add(new int[]{i, j});
                }
                if (map[i][j] == 1) {
                    house.add(new int[]{i, j});
                }
            }
        }
        int[] choice = new int[m];
        int result = dfs(m, map, n, shop, house,choice,0);
        System.out.println(result);
    }

    private static final int INF = 987654321;

    private static int dfs(int depth, int[][] map, int n, List<int[]> shop, List<int[]> house, int[] choice,int start) {
        if (depth == 0) {
            int result = 0;
            for(int[] housePoint : house){
                int temp = INF;
                for(int num : choice){
                    int[] shopPoint = shop.get(num);
                    int y = shopPoint[0];
                    int x = shopPoint[1];
                    temp = Math.min(Math.abs(housePoint[0] - shopPoint[0]) + Math.abs(housePoint[1] - shopPoint[1]),temp);
                }
                result += temp;
//                System.out.println(result);
            }
            return result;
        }
        int result = INF;
        for (int i = start; i < shop.size(); i++) {
            choice[depth-1] = i;
            result = Math.min(dfs(depth - 1, map, n, shop, house,choice,i + 1), result);
        }
        return result;
    }
}