백준 15886번 치킨 배달 자바

치킨 배달 문제 보러가기

문제 설명

자바 코드

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

public class Main {
    static int N;
    static int M;
    static BufferedReader br;
    static int result;
    static boolean[] chk;
    static List<Point> chickenPoint;
    static List<Point> housePoint;
    public static void main(String[] args) throws Exception{
        br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer strTok=new StringTokenizer(br.readLine(), " ");
        N=Integer.parseInt(strTok.nextToken());
        M=Integer.parseInt(strTok.nextToken());
        chickenPoint=new ArrayList<Point>();
        housePoint=new ArrayList<Point>();
        initCity();
        result=Integer.MAX_VALUE;
        chk=new boolean[chickenPoint.size()];
        dfs(0,0);
        System.out.println(result);
    }

    static void minChicken(List<Point> select){
        int cityDis=0;
        for(Point hp:housePoint){
            int hr=hp.x; 
            int hc=hp.y;
            int chikenDis=Integer.MAX_VALUE;
            for (Point point:select) {
                int cr=point.x;
                int cc=point.y;
                int chk=Math.abs(hr-cr)+Math.abs(hc-cc);
                chikenDis=Math.min(chk,chikenDis);
            }
            cityDis+=chikenDis;
        }
       result=Math.min(result,cityDis);

    }

    static void dfs(int depth,int start){
        if(depth==M){
            List<Point> select=new ArrayList<Point>();
            for(int i=0;i<chickenPoint.size();i++){
                if(chk[i]) select.add(chickenPoint.get(i));
            }
            minChicken(select);
            return;
        }
        for(int i=start;i<chickenPoint.size();i++){
            chk[i]=true;
            dfs(depth+1,i+1);
            chk[i]=false;
        }
    }

    static void initCity() throws Exception{
        for(int i=1;i<=N;i++){
            StringTokenizer strTok=new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=N;j++){
                int point=Integer.parseInt(strTok.nextToken());
                if(point==2){
                    chickenPoint.add(new Point(i,j)); 
                }else if(point ==1){
                    housePoint.add(new Point(i,j));
                }
            }
        }
    } 
}

class Point {
    int x;
    int y;

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

문제 풀이

백트레킹을 이용하여 접근합니다.

치킨 갯수 M 값을 백트레킹으로 구하여 해당 최대값 M이 될때마다 도시거리를 구하고 min값으로 출력해주면 됩니다.

• M 값을 구하는 백트레킹 알고리즘 구현
• M 값을 구할때 마다 도시거리를 구함
• 도시거리를 비교하여 최소값을 출력

감사합니다.