[java 백준] 골드 5/ 15686번 치킨배달

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

15686번: 치킨 배달

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
    public static int n;
    public static int m;
 
 
    public static class Node{
        int x;
        int y;
        public Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
 
    public static int arr[][];
    public static ArrayList<Node>home=new ArrayList<Node>();
    public static ArrayList<Node>chicken=new ArrayList<Node>();
 
    public static int chickenSize;
    public static int homeSize;
    public static int ans=(int)1e9;
    public static boolean visited[];
    
    //이때 n은 치킨집의 개수
    public static void backTracking(boolean[]visited,int depth,int n,int r){
 
        if(r==0){
 
 
            print(visited);
            return ;
        }
        for(int i=depth;i<n;i++){
            visited[i]=true;
            backTracking(visited,i+1,n,r-1);
            visited[i]=false;
        }
    }
 
    public static void print(boolean[]visited){
 
        int num=0;
 
        for(int j=0;j<homeSize;j++){
            int min=(int)1e9;
            for(int i=0;i<chickenSize;i++){
                if(visited[i]==true){
                    int temp=Math.abs(home.get(j).x-chicken.get(i).x)+Math.abs(home.get(j).y-chicken.get(i).y);
                    min=Math.min(temp,min);
 
 
                }
            }
            num+=min;
 
 
        }
        ans=Math.min(ans,num);
 
 
 
 
 
 
    }
 
    public static void main(String args[]) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        //기본적으로 치킨을 중심으로 집까지의 거리를 계산해서 배열에 넣을 것
        // 치킨집만 m개 만큼 선택해서 더 작은 값을 답으로 출력 할 것
 
        st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        arr=new int[n+1][n+1];
 
 
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                arr[i][j]=Integer.parseInt(st.nextToken());
            }
        }
 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(arr[i][j]==1){
                    home.add(new Node(i,j));
                }else if(arr[i][j]==2){
                    chicken.add(new Node(i,j));
                }
            }
        }
 
 
 
        chickenSize=chicken.size();
        homeSize=home.size();
        visited=new boolean[chickenSize+1];
        for(int i=0;i<chickenSize;i++){
            backTracking(visited,0,chickenSize,m);
        }
        System.out.println(ans);
 
 
        //미리 치킨집 선택? --> 백트래킹
        
 
 
 
 
 
 
 
 
 
    }
 
}
 

 

nCr의 조합을 푸는 방법은 재귀도 있지만 백트래킹도 있다!

 

 for(int i=depth;i<n;i++){

            visited[i]=true;

            backTracking(visited,i+1,n,r-1);

 

            visited[i]=false;

        }

이 부분이 백트래킹을 구현한 것인데 뽑았으면 visited[i]=true로 해주고, 백트래킹 함수를 실행시켜준 다음에 뽑은 걸 다시 안뽑은 상태로 만들어준다. (다시 이전 상태로 되돌리는거 -> 백트래킹)

 

r=0일 때 뽑은 애들의 상태를 저장하는 visited배열만 print함수로 넘겨줘서 거기서 최솟값을 찾아준다. 

https://minhamina.tistory.com/38

[Java] 조합 Combination