15686. 치킨 배달

문제 개요

주어진 위치들을 토대로 M개의 거점 노드에서 다른 일반 노드들간의 최소 거리의 합을 구하는 문제입니다.

문제 접근

문제를 보면서 네트워크 시간에 배웠던 라우팅이 이런식으로 이루어지지 않을까 생각이 들었습니다.
처음에는 MST처럼 그리디로 해결할 수 있지 않을까 생각했었는데, 생각해보니 그리디 조건이 성립하지 않았습니다.
그래서 결국 브루트포스로 해결하였습니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

class Position implements Comparable<Position>{
    private int row;
    private int col;

    public Position(int row, int col){
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getCol() {
        return col;
    }

    public void setCol(int col) {
        this.col = col;
    }

    public static int distance(Position a, Position b){
        return Math.abs(a.col-b.col) + Math.abs(a.row-b.row);
    }

    @Override
    public int compareTo(Position o) {
        return distance(this, o);
    }
}

public class Main {
    static List<Position> chickens;
    static List<Position> homes;
    static int N, M;

    static void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] NM = bf.readLine().split(" ");
        N = Integer.parseInt(NM[0]);
        M = Integer.parseInt(NM[1]);
        chickens = new ArrayList<>();
        homes = new ArrayList<>();

        for(int i=0;i<N;i++){
            int j=0;
            for(String pos : bf.readLine().split(" ")){
                if(pos.equals("1")){
                    homes.add(new Position(i, j));
                }
                if(pos.equals("2")){
                    chickens.add(new Position(i, j));
                }
                j++;
            }
        }
    }

    static int tracking(List<Position> selected, int last){
        int result = 9999;
        if(selected.size() == M){
            int sum = 0;
            for(var home : homes){
                sum += selected.stream().map(chicken -> Position.distance(chicken, home)).collect(Collectors.minBy(Integer::compareTo)).get();
            }
            return sum;
        }
        for(int i=last+1; i<chickens.size();i++){
            selected.add(chickens.get(i));
            result = Math.min(tracking(selected, i), result);
            selected.remove(chickens.get(i));
        }
        return result;
    }

    static void process(){
        System.out.println(tracking(new ArrayList<>(), -1));
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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