[PS] BOJ15686 치킨 배달 ( 백트래킹 ) with JAVA

 

15686번: 치킨 배달

 

◎ 문제풀이

 

2차원 배열에 존재하는 치킨집들에서 M개의 경우를 선택하여 그중 치킨거리가 최소인 거리를 구하는 것이다.

N개중 M개를 뽑는 모든 경우를 탐색하는 가장 좋은 방법은 재귀호출을 이용하는 것이다. 재귀호출을 이용하여 가장 적합한 경우를 구하는 문제는 백트래킹(BackTracking)을 활용하면 좋다. 

 

백트래킹은 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다.

 

 

1) 재귀호출로 치킨집 M개를 탐색한다.

2) 치킨집 M개와 모든 집 사이의 거리의 최소거리를 구한다. 

3) 모든 치킨집 M개 경우를 백트래킹하여 최소거리를 구한다. 

 

 

◎ 코드

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

public class Main {

    static int n,m;
    static int[][] matrix;
    static List<int[]> houses;
    static List<int[]> chickenStores;
    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;


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

        matrix = new int[n][n];
        houses = new ArrayList<>();
        chickenStores = new ArrayList<>();

        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());
                matrix[i][j] = value;

                if(value==1) houses.add(new int[]{i,j});
                if(value==2) chickenStores.add(new int[]{i,j});
            }
        }

        visited = new boolean[chickenStores.size()];
        backtracking(0,0);

        System.out.println(ans);

    }

    public static void backtracking(int size, int index){

        if(size == m){
            int result = 0;
            for(int i=0;i<houses.size();i++){
                int[] house = houses.get(i);
                int dist = Integer.MAX_VALUE;
                for(int j=0;j<chickenStores.size();j++){
                    if(!visited[j]) continue;
                    int[] chickenStore = chickenStores.get(j);
                    dist = Math.min(dist, Math.abs(chickenStore[0]-house[0])+Math.abs(chickenStore[1]-house[1]));
                }
                result += dist;
            }
            ans = Math.min(ans,result);
            return;
        }

        for(int i=index;i<chickenStores.size();i++){
            if(visited[i]) continue;
            visited[i] = true;
            backtracking(size+1,i);
            visited[i] = false;
        }
    }
}