[DFS] 치킨배달(2번째)

백준 15686 치킨배달 (삼성 SW역량테스트)

https://www.acmicpc.net/submit/15686/10568790

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int M;
    static List<Position> homes = new ArrayList<>();
    static List<Position> chickens = new ArrayList<>();
    static int minValue=Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                int a = Integer.parseInt(st.nextToken());

                if(a==1) homes.add( new Position(i,j));
                else if(a==2) chickens.add(new Position(i,j));

            }
        }

        dfs(0,0, new Stack<>());
        System.out.println(minValue);
    }

    //M개의 치킨조합을 찾는다
    static void dfs(int index, int target, Stack<Position> s){

        if(index==M){
            minValue = Math.min(minValue, getChickenSum(s)); //하나의 M개 치킨집 조합을 조사
            return;
        }

        for(int i=target; i<chickens.size(); i++){
            s.add( chickens.get(i) );
            dfs(index+1, i+1, s);
            s.pop();
        }
    }


    //입력받은 치킨집으로 각 집에서의 치킨거리 합을 구한다
    static int getChickenSum(Stack<Position> chi){

        int sum=0;

        for(Position h: homes){

            int minDistance=Integer.MAX_VALUE; //거리가 젤 짧은게 치킨거리
            for(Position c: chi){
                minDistance = Math.min(minDistance, getChickenDistance(h,c));
            }
            sum += minDistance;
        }
        return sum;
    }

    static int getChickenDistance(Position p1, Position p2){
        return Math.abs(p1.n-p2.n) + Math.abs(p1.m-p2.m);
    }


    static class Position{
        int n;
        int m;
        Position(int n, int m){
            this.n = n;
            this.m = m;
        }
    }
}

치킨거리 구하기

//입력받은 치킨집으로 각 집에서의 치킨거리 합을 구한다
static int getChickenSum(Stack<Position> chi){

    int sum=0;

    for(Position h: homes){

        int minDistance=Integer.MAX_VALUE; //거리가 젤 짧은게 치킨거리
        for(Position c: chi){
            minDistance = Math.min(minDistance, getChickenDistance(h,c));
        }
        sum += minDistance;
    }
    return sum;
}

치킨거리를 구할때 BFS나 DFS로 할 필요없이 집이랑 치킨집 거리를 바로 구하면 된다.

경우 찾기

//M개의 치킨조합을 찾는다
static void dfs(int index, int target, Stack<Position> s){

    if(index==M){
        minValue = Math.min(minValue, getChickenSum(s)); //하나의 M개 치킨집 조합을 조사
        return;
    }

    for(int i=target; i<chickens.size(); i++){
        s.add( chickens.get(i) );
        dfs(index+1, i+1, s);
        s.pop();
    }
}

기존에 사용하던 조합 코드보다는 이 코드가 더 나은 것 같다.

큐, DFS를 활용한 백트래킹.