문제 풀이(52)

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

import java.util.*;
import java.io.*;


class Node{
    int x;
    int y;
    PriorityQueue<Integer>dist = new PriorityQueue<>();

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

   
}

public class Main {


    static int N, M,min;
    static int[] selected;
    static boolean[] used;
    static ArrayList<Node>home = new ArrayList<>();
    static ArrayList<Node>chicken = new ArrayList<>();

    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());

        selected = new int[M];

        used = new boolean[M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
            
                int value = Integer.parseInt(st.nextToken());

                if (value == 1 ) {
                    home.add(new Node(i, j));
                }else if (value == 2) {
                    chicken.add(new Node(i, j));
                }
            }
        }

        min = Integer.MAX_VALUE;

        rec_func(0,0);

        System.out.println(min);
    }

    public static void rec_func(int k,int idx)
    {
        if (k == M) {
        
            for (int i = 0; i < selected.length; i++) {
                Node now = chicken.get(selected[i]);
            
             
                for (int j = 0; j < home.size(); j++) {
                    
                    Node tmp = home.get(j);

                    int value = Math.abs(now.x - tmp.x) + Math.abs(now.y - tmp.y);

                    if (!home.get(j).dist.isEmpty() && value <= home.get(j).dist.peek()) {
                        home.get(j).dist.clear();
                        home.get(j).dist.add(value);
                    }else if(home.get(j).dist.isEmpty()){
                        home.get(j).dist.add(value);
                    }

                }
            }

            int sum = 0;

           
            for (int i = 0; i < home.size(); i++) {

                sum += home.get(i).dist.poll();                           
            }

            min = Math.min(min, sum);

        }else{
            for (int i = idx; i < chicken.size(); i++) {
            
                selected[k] = i;
                rec_func(k + 1, i + 1);
                selected[k] = 0;
            }
        }
    }

}

rec_func 메서드
rec_func는 재귀 함수로, 가능한 모든 치킨집 조합을 생성하고 각 조합에 대해 치킨 거리를 계산한다.
k: 현재까지 선택된 치킨집의 수이다.
idx: 다음에 선택될 치킨집의 인덱스이다.
이 함수는 선택된 치킨집 수 k가 M과 같아지면 모든 집에 대해 가장 가까운 치킨집과의 거리를 계산하고, 이 거리들의 합을 min과 비교하여 최소값을 업데이트한다. 모든 집들이 dist 큐를 갖기 때문에, 각 집에서 가장 가까운 치킨집의 거리는 큐의 맨 앞 요소로 간주된다.