BOJ_G5_15686

📁 [G5_15686] 치킨 배달

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

public class Main {
    static class Dot{
        int x;
        int y;

        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int N,M;
    static int[][] map;
    static ArrayList<Dot> mList;
    static ArrayList<Dot> cList;
    static int min = Integer.MAX_VALUE;
    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());

        map = new int[N][N];
        cList = new ArrayList<>();
        mList = new ArrayList<>();

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                // 치킨집인 경우 리스트에 담기
                if(map[i][j] == 2) cList.add(new Dot(j,i));
            }
        }
        
        // 조합
        Comb(0,0);
        System.out.println(min);

    }
    
    // 조합
    static void Comb(int idx, int start){
        // 기저조건
        if(idx == M){
            // 최소 도시 치킨 거리 구하기
            min = Math.min(chLength(), min);
            return;
        }
        
        for(int i=start; i<cList.size(); i++){
            // M개 선택된 리스트에 좌표 추가하기
            mList.add(cList.get(i));
            Comb(idx+1, i+1);
            // 기저조건
            mList.remove(mList.size()-1);
        }
    }
    
    // 최소 도시 치킨 거리 구하기
    static int chLength(){
        // 도시 치킨 거리
        int sum = 0;

        // 전체 돌면서 1일 때 계산해주기
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                // 만약 집인 경우
                if(map[i][j] == 1){
                    // 가장 짧은 치킨 거리
                    int chickenLength = Integer.MAX_VALUE;
                    // M 만큼 돌면서 길이 체크
                    for(int z=0;z<mList.size();z++){
                        // 치킨집 좌표
                        int x = mList.get(z).x;
                        int y = mList.get(z).y;

                        // 좌표 계산
                        int length = Math.abs(x-j)+ Math.abs(y-i);
                        // 최솟값 구하기
                        chickenLength = Math.min(chickenLength, length);
                    }
                    // 가장 짧은 치킨 거리 더하기
                    sum += chickenLength;
                }
            }
        }
        return sum;
    }
}

🤔 나의 생각

구현 문제이다.
이 문제의 포인트는 조합으로 M개의 치킨집을 정하고 각 집에서부터 M개의 치킨집까지의 치킨거리를 구한 뒤 도시의 치킨거리를 구해주면 된다.
그리고 최대 M개의 치킨집이라서 1부터 M개 다 구해야하는 것으로 착각할 수 있는데 어차피 치킨집이 많으면 많을 수록 도시의 치킨거리는 더 짧아지기 때문에 무조건 M개의 치긴집의 치킨거리를 구하는게 베스트다.
오랜만에 조합을 이용하는거라 좀 헤맸지만 … 순서대로 해결해 나가면 해결할 수 있다.