[Java] 백준 15686 치킨 배달

문제

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

15686번: 치킨 배달

알아야 할 개념

• DFS 백트래킹 

풀이

 

핵심은 치킨집을 (Math.min (M, 치킨집 개수 ) ) 만큼 뽑았을 때 도시 치킨 거리의 수를 모두 구하면 되는 문제.

 

나이브한 브루트포스 풀이 알고리즘은 다음과 같다.

1. 일정 개수 (min(주어진 M, 치킨집 개수 )) 만큼 치킨집을 뽑는다.
2. 모든 집의 치킨 거리를 계산한다.
3. 도시 치킨 거리를 계산한다.
4. 알고리즘 (1,2,3) 의 모든 경우의 수에 대해 최솟값을 도출한다.

 

 

파이썬엔 컴비네이션이 있지만, 자바는 구현해야한다. (코테 풀때 급할 수록 돌아가라는 뜻인가)

재귀 함수 dfs로 알고리즘(1,2,3) 을 구현했다. 각 Level(재귀 함수 레벨) 에서 치킨집을 하나 리스트에 담은 후 재귀 함수를 호출한다. 호출이 끝난 후에는 현재 Level에서 치킨집 리스트에 담긴 마지막 치킨집을 제거하고 다음 node로 넘어간다.

        for(int i =start  ;i < storeList.size() ;i++){
            selectedStore.add(i);   //하나 추가
            dfs(selectedStore, level+1, i+1,max);//재귀 탐색
            selectedStore.remove(selectedStore.size()-1);   //마지막 리스트에서 빼기
        }

 

이해를 위한 그림

치킨집 개수 3 이고 최대 2개 뽑는 상황일 때 백트래킹 과정이다. 탐색 번호를 1부터 11로 매겼다.

 

각 치킨집을 다 뽑았으면, 도시 치킨 거리를 계산하고 재귀 호출을 더이상 하지 않는다. 

if(level == max){//종료 조건.리프 노트 일때
            int ret =0 ;
                for(int[] home : homeList){
                    int dis = Integer.MAX_VALUE;
                    for(int select: selectedStore){
                        dis = Math.min(
                                Math.abs(home[0]- storeList.get(select)[0]) + Math.abs(home[1]- storeList.get(select)[1])
                                ,dis);
                    }
                    ret += dis;//ret는 도시 치킨 거리
                }
            answer = Math.min(ret, answer);//answer 업데이트
            return;	//재귀호출 더 안함
        }

전체 치킨집 개수보다, 뽑는 것이 많을 때 예외처리를 해주었다. 

dfs(new ArrayList<Integer>(), 0, 0, Math.min(m, storeList.size()));

 

코드

package solve;

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

public class Main {
    List<int[]> homeList;   // 가정집 리스트
    List<int[]> storeList;  // 치킨집 리스트
    int answer = Integer.MAX_VALUE;     //최솟값 구해야함으로 최댓값으로 초기화

    public static void main(String args[]) throws IOException {
        Main m = new Main();
        System.out.println(m.solve());
    }
    public int solve()throws IOException{
        //입력을 받는다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());//최대 치킨집 개수

        int [][] map = new int[n][n];
        homeList = new ArrayList<int[]>();
        storeList = new ArrayList<>();
        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){ //가정집 리스트에 추가
                    homeList.add(new int[]{i, j});//x, y 좌표 추가
                }else if(map[i][j] == 2){
                    storeList.add(new int[]{i,j});
                }
            }
        }

        dfs(new ArrayList<Integer>(), 0, 0, Math.min(m, storeList.size()));
        return answer;
    }

    public void dfs(List<Integer> selectedStore, int level, int start, int max){
        if(level == max){//종료 조건.리프 노트 일때
            int ret =0 ;
                for(int[] home : homeList){
                    int dis = Integer.MAX_VALUE;
                    for(int select: selectedStore){
                        dis = Math.min(
                                Math.abs(home[0]- storeList.get(select)[0]) + Math.abs(home[1]- storeList.get(select)[1])
                                ,dis);
                    }
                    ret += dis;//ret는 도시 치킨 거리
                }
            answer = Math.min(ret, answer);//answer 업데이트
            return;
        }

        for(int i =start  ;i < storeList.size() ;i++){
            selectedStore.add(i);   //하나 추가
            dfs(selectedStore, level+1, i+1,max);//재귀 탐색
            selectedStore.remove(selectedStore.size()-1);   //마지막 리스트에서 빼기
        }
    }
}