[백준 15686번] 치킨 배달 :: 늦깎이 IT

[백준 15686번 치킨배달 URL]

사실 크게 어려운 문제는 아닙니다만, 여러 후보군 중에서 몇가지만을 선택하는 방법을 모르는 경우에는

조금 난해할 수 있습니다. 이 문제에서 핵심인 K개의 치킨집이 있을 때 이중 M개만을 선택하고 다른 치킨집들을

모두 폐업시켜야 하는 것입니다. M 개중에 K개를 선택하는 방법은 DFS를 활용하여 구현할 수 있습니다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, M, ans = Integer.MAX_VALUE;
    public static int[][] map;
    public static List<Node> houses;
    public static List<Node> chickens;
    public static boolean[] selected;
    public static int[] dirX = new int[] { 0, 0, -1, 1 };
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
        houses = new ArrayList<Node>();
        chickens = new ArrayList<Node>();
 
        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] == 1)
                    houses.add(new Node(i, j));
                else if (map[i][j] == 2)
                    chickens.add(new Node(i, j));
            }
        }
        selected = new boolean[chickens.size() + 1];
        dfs(0, 0);
        System.out.println(ans);
 
    }
 
    public static void dfs(int depth, int numOfSelect) {
        
        if (depth > chickens.size())
            return;
 
        if (numOfSelect == M) {
 
            int sumOfDist = 0;
 
            for (int i = 0; i < houses.size(); i++) {
 
                int dist = Integer.MAX_VALUE;
 
                for (int j = 0; j < chickens.size(); j++) {
 
                    if (selected[j]) {
 
                        Node house = houses.get(i);
                        Node chicken = chickens.get(j);
                        dist = Math.min(dist, Math.abs(house.row - chicken.row) + Math.abs(house.col - chicken.col));
 
                    }
                }
                sumOfDist += dist;
            }
            ans = Math.min(ans, sumOfDist);
            return;
        }
 
        
 
        selected[depth] = true;
        dfs(depth + 1, numOfSelect + 1);
 
        selected[depth] = false;
        dfs(depth + 1, numOfSelect);
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
}
 
class Node {
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}