BJ G5 15686 치킨배달

BJ G5 15686 치킨배달

 

 

문제링크

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

15686번: 치킨 배달

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

 * 용어에 대한 정리가 필요
   -- 치킨 거리: 집과 가장 가까운 치킨 집 사이의 거리
   -- 도시의 치킨 거리: 도시에 있는 모든 집의 치킨 거리의 합
 

 * 선택의 문제
   -- 전체 치킨집의 개수 중 M 개를 선택하는 문제, 순서는 무관하기 때문에 조합적 선택
   -- 전체 치킨집에서 M개를 선택하기 위해 치킨집의 목록을 관리하자.
    
 * 거리의 계산
   -- 거리는 간단히 |r1-r2| + |c1-c2|로 구현   
   -- 모든 집들에서 선택된 치킨집과의 거리를 구해봐야 하기 때문에 치킨 집과 마찬가지로 집들의 목록을 관리하자.

입력사항

 * 도시의 크기: N(2 ≤ N ≤ 50)
 * 치킨집의 개수: M(1 ≤ M ≤ 13)
 * 도시의 정보는 0, 1, 2로 이루어져 있고, 
 * 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 
 * 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력사항

 * 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=KXFhfytgj5E&t=81s

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class BJ_15686_G5_치킨배달 {

    private static int N;// 지도의 크기
    private static int M;// 남길 치킨집 수

    private static List<Point> chickenShops, homes; // 각각 치킨집과 집
    private static int MinChickenDist = Integer.MAX_VALUE; // 최소 치킨 거리

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));
        StringTokenizer temp = new StringTokenizer(br.readLine());
        N = Integer.parseInt(temp.nextToken()); // 지도의 크기: N(2 ≤ N ≤ 50)
        M = Integer.parseInt(temp.nextToken()); // 남길 치킨집 수: M(1 ≤ M ≤ 13)

        // 치킨집 집으로 구분해보기.
        chickenShops = new ArrayList<>();
        homes = new ArrayList<>();

        for (int r = 1; r <= N; r++) {
            temp = new StringTokenizer(br.readLine());
            for (int c = 1; c <= N; c++) {
                Integer info = Integer.parseInt(temp.nextToken());
                if (info.equals(1)) {
                    homes.add(new Point(r, c));
                } else if (info.equals(2)) {
                    chickenShops.add(new Point(r, c));
                }
            }
        }

        // System.out.println("chicken: " + stores);
        // System.out.println("home: " + homes);

        chickenShopCombination(0, M, new Point[M]);

        // 가능한 두 곳의 치킨 집을 찾아보자.
        System.out.println(MinChickenDist);
    }

    public static void chickenShopCombination(int si, int ti, Point[] temp) {
        if (ti == 0) {
            // System.out.println(Arrays.toString(temp));
            check(temp);
        } else {
            for (int i = si; i < chickenShops.size(); i++) {
                temp[ti - 1] = chickenShops.get(i);
                chickenShopCombination(i + 1, ti - 1, temp);
            }
        }
    }

    /**
     * 집에서 각 임시 지점까지의 최단 거리의 합을 찾아서 업데이트 해보자.
     * 
     * @param tempShops
     */
    public static void check(Point[] tempShops) {
        int distSum = 0;
        for (Point home : homes) {
            int minDist = Integer.MAX_VALUE;
            for (Point store : tempShops) {
                int dist = Math.abs(store.row - home.row) + Math.abs(store.col - home.col);
                minDist = Math.min(dist, minDist);
            }
            distSum += minDist;
        }
        MinChickenDist = Math.min(MinChickenDist, distSum);
    }

    static class Point {
        int row, col;

        public Point(int r, int c) {
            this.row = r;
            this.col = c;
        }

        @Override
        public String toString() {
            return "[" + row + ", " + col + "]";
        }

    }

    private static String src = "5 1\r\n" +
                                "1 2 0 2 1\r\n" +
                                "1 2 0 2 1\r\n" +
                                "1 2 0 2 1\r\n" +
                                "1 2 0 2 1\r\n" +
                                "1 2 0 2 1";
}