백준 15686

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

15686번: 치킨 배달

🍺 메인로직

치킨 집 중 1개씩 고르기(isSelected[i] = true), 고르는 로직 반복 -> 최종 m개가 되면 거리 count -> 각 count 받아서 계속 answer과 비교해서 count로 갱신 -> 정답 출력 

 

🍺 필요한 변수들 

static ArrayList<Pos> home;
static ArrayList<Pos> store;
static boolean[] isSelected;
static int n, m, answer;
// answer는 Integer.MAX_VALUE로 초기화

좌표 클래스도 정의해두었다. 

public static class Pos {
	int x;
    int y;
    Pos (int x, int y) {
    	this.x = x;
        this.y = y;
    }
}

 

🍺 메서드

- 메인 : 데이터 입력받기, 위의 정적 변수들 초기화, combination(0,0) 수행 , 결과 출력 

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());
        home = new ArrayList<>();
        store = new ArrayList<>();
        answer = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int temp = Integer.parseInt(st.nextToken());
                if (temp == 1) {
                    home.add(new Pos(i, j));
                }
                else if (temp == 2) {
                    store.add(new Pos(i, j));
                }
            }
        }

        isSelected = new boolean[store.size()];
        combination(0, 0);
        System.out.println(answer);
    }

- countDis (Pos home, Pos chicken) : 장소 사이 거리  계산

public static int countDis(Pos home, Pos chicken) {
        return Math.abs(home.x - chicken.x) + Math.abs(home.y - chicken.y);
}

- combination(int cur, int count) : cur은 현재 몇 번 인덱스까지 뽑혔는지, count는 몇개 뽑았는지. count==m이 되면 chickenDistance()함수 수행 

public static void combination(int cur, int chickenNum) {
        // 다 뽑은 상태라면 각 집별로 치킨집과의 거리 계산
        if (chickenNum == m) {
            answer = Math.min(answer, chickenDistance());
            return;
        }
        for (int i = cur; i < store.size(); i++) {
            isSelected[i] = true;
            combination(i+1, chickenNum+1);
            // 재귀가 끝나면 다시 false
            isSelected[i] = false;
        }
}

 

- chickenDistance() : 현재 뽑힌 치킨집들로 모든 집과의 치킨거리 countDis() -> 최솟값들만 더해서 치킨거리 리턴

public static int chickenDistance() {
        int result = 0; // 현재 뽑힌 치킨집들로 모든 집과의 치킨 거리를 잰 최솟값의 합
        for (int i = 0; i < home.size(); i++) {
            int temp = Integer.MAX_VALUE; // temp가 한 집당 모든 치킨집과의 거리를 재는 용
            for (int j = 0; j < store.size(); j++) {
                if (isSelected[j]) {
                    temp = Math.min(temp, countDis(home.get(i), store.get(j)));
                }
            }
            result += temp;
        }
        return result;
}