[백준 15686, Java] 치킨 배달

문제

 

15686번: 치킨 배달

 

풀이

 

최대 M개에 대한 치킨집에 대해서 각 집의 치킨거리의 합을 구한다음 구한 치킨거리 중 최솟값을 구하면 된다

그러려면 우선 지도에 있는 치킨 집 중에서 1~M개의 치킨집을 선택해야한다. 이 문제는 

 

15650번: N과 M (2)

위의 문제와 같다. 그런 다음 선택한 치킨집에 대해서 각각의 집과 치킨거리를 구해야한다. 처음에 이 부분을 하나의 집에 대해서 치킨집까지 최소거리를 BFS로 탐색을 했더니 시간초과가 났다. 맵을 복사하는 것 때문인 것 같다

 

 거리를 구하는 건 문제에 나와있는대로 하면 된다. ((2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2) 너무 어렵게 생각하지말고 문제를 다시 읽어보기!

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

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

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}
public class Main {
    static int N;
    static int M;
    static final int EMPTY = 0;
    static final int HOUSE = 1;
    static final int CHICKEN_STORE = 2;
    static ArrayList<Point> houses;
    static ArrayList<Point> chickenStores;
    static int distance = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st  = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        houses = new ArrayList<>();
        chickenStores = new ArrayList<>();
        for(int r =0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<N; c++){
                int value = Integer.parseInt(st.nextToken());
                if(value==HOUSE){
                    houses.add(new Point(r, c));
                }
                else if(value ==CHICKEN_STORE){
                    chickenStores.add(new Point(r, c));
                }
            }
        }

        //전체 치킨스토어에서 1~M개 선택
        ArrayList<Point> cnadidate = new ArrayList<>();
        for(int pickCount = 1; pickCount<=M; pickCount++){
            pickStore(pickCount, 0, 0, cnadidate);
        }

        bw.write(String.valueOf(distance));
        bw.flush();

    }

    static void pickStore(int pickCount, int index, int count,ArrayList<Point> candidates){
        if(count>=pickCount){
            int chickenDistance = calculateDistance(candidates);
            distance = Math.min(distance, chickenDistance);
        }
        else if(index>=chickenStores.size()){
            return;
        }
        else {
            candidates.add(chickenStores.get(index));
            pickStore(pickCount, index+1, count+1, candidates);

            candidates.remove(candidates.size()-1);
            pickStore(pickCount, index+1, count, candidates);
        }
    }
    static int calculateDistance(ArrayList<Point> candidates){
        int totalChickenDistance = 0;
        for (Point house : houses) {
            int currentHouseDistance = Integer.MAX_VALUE;

            for (Point chickenStore : candidates) {
                int distance = Math.abs(house.x - chickenStore.x) + Math.abs(house.y - chickenStore.y);
                currentHouseDistance = Math.min(currentHouseDistance, distance);
            }
            totalChickenDistance += currentHouseDistance;
        }
        return totalChickenDistance;
    }
}