백준 15686번 치킨 배달

 문제 링크 : https://www.acmicpc.net/problem/15686

입력으로는

집은 1, 치킨집은 2, 빈공간은 0으로 나태고있는 n사이즈의 맵과

골라야학 치킨집의 갯수 m이 주어진다.

맵에 존재하는 치킨집중 m개를 선택하였을때 도시의 치킨거리의 최솟값을 출력하는 문제이다.

(자세한 설명은 분제링크를 참조하세요)

아무튼 그래서 나는 우선 입력받으며 집의 목록과 치킨집의 목록을 각각 ArrayList에 저장하였다.

치킨집의 전체 갯수에서 m개를 선택하는 모든경우를 구하였고.

각각의 경우마다 치킨거리를 구해주었고 그중 최소값을 찾아 출력하였다.

아래는 소스코드이다.

기저 사례에 해당하는 내용이 길어지니까 가독성이 떨어지는것같다. 다음부터는 함수로 따로 빼야겠다.

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    static int m, minSum;
    static ArrayList<Point> house = new ArrayList<Point>();
    static ArrayList<Point> beer = new ArrayList<Point>();
    static ArrayList<Integer> selected = new ArrayList<Integer>();
    
    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                int p = sc.nextInt();
                if(p==1) house.add(new Point(i, j));
                else if(p==2) beer.add(new Point(i, j));
            }
        }
        
        minSum = Integer.MAX_VALUE;
        pick(m);
        System.out.println(minSum);
    }
    
    
    public static void pick(int toPick) {
        if(toPick == 0) {
            int sum = 0;
            
            for(int i=0; i<house.size(); i++) {
                int minHouseToBeer = Integer.MAX_VALUE;
                
                for(int j=0; j<selected.size(); j++) {
                    Point houseP = house.get(i);
                    Point beerP = beer.get(selected.get(j));
                    int distance = calc(houseP, beerP);
                    minHouseToBeer = Math.min(minHouseToBeer, distance);
                }
                
                sum += minHouseToBeer;
            }
            
            minSum = Math.min(minSum, sum);
            return;
        }
        
        int small = selected.isEmpty() ? 0 : selected.get(selected.size()-1) + 1;
        // 0 부터
        for(int i=small; i<beer.size(); i++) {
            selected.add(i);
            pick(toPick - 1);
            selected.remove(selected.size()-1);
        }
    }
    
    public static int calc(Point a, Point b) {
        int r1 = a.y - b.y;
        if(r1<0) r1 *= -1;
        
        int r2 = a.x - b.x;
        if(r2<0) r2 *= -1;
        
        return r1 + r2;
    }
    
}
 
class Point {
    int y, x;
    
    Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
    
    public String toString() {
        String s = "("+y+", "+x+")";
        return s;
    }
}